

<!DOCTYPE html>

<html>
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>6. Kaleidoscope: Extending the Language: User-defined Operators &#8212; LLVM 9 documentation</title>
    <link rel="stylesheet" href="../_static/llvm-theme.css" type="text/css" />
    <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
    <script id="documentation_options" data-url_root="../" src="../_static/documentation_options.js"></script>
    <script src="../_static/jquery.js"></script>
    <script src="../_static/underscore.js"></script>
    <script src="../_static/doctools.js"></script>
    <script src="../_static/language_data.js"></script>
    <link rel="index" title="Index" href="../genindex.html" />
    <link rel="search" title="Search" href="../search.html" />
    <link rel="next" title="7. Kaleidoscope: Extending the Language: Mutable Variables" href="OCamlLangImpl7.html" />
    <link rel="prev" title="5. Kaleidoscope: Extending the Language: Control Flow" href="OCamlLangImpl5.html" />
<style type="text/css">
  table.right { float: right; margin-left: 20px; }
  table.right td { border: 1px solid #ccc; }
</style>

  </head><body>
<div class="logo">
  <a href="../index.html">
    <img src="../_static/logo.png"
         alt="LLVM Logo" width="250" height="88"/></a>
</div>

    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="OCamlLangImpl7.html" title="7. Kaleidoscope: Extending the Language: Mutable Variables"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="OCamlLangImpl5.html" title="5. Kaleidoscope: Extending the Language: Control Flow"
             accesskey="P">previous</a> |</li>
  <li><a href="http://llvm.org/">LLVM Home</a>&nbsp;|&nbsp;</li>
  <li><a href="../index.html">Documentation</a>&raquo;</li>

          <li class="nav-item nav-item-1"><a href="index.html" accesskey="U">LLVM Tutorial: Table of Contents</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href=""><span class="section-number">6. </span>Kaleidoscope: Extending the Language: User-defined Operators</a></li> 
      </ul>
    </div>


    <div class="document">
      <div class="documentwrapper">
          <div class="body" role="main">
            
  <div class="section" id="kaleidoscope-extending-the-language-user-defined-operators">
<h1><span class="section-number">6. </span>Kaleidoscope: Extending the Language: User-defined Operators<a class="headerlink" href="#kaleidoscope-extending-the-language-user-defined-operators" title="Permalink to this headline">¶</a></h1>
<div class="contents local topic" id="contents">
<ul class="simple">
<li><p><a class="reference internal" href="#chapter-6-introduction" id="id1">Chapter 6 Introduction</a></p></li>
<li><p><a class="reference internal" href="#user-defined-operators-the-idea" id="id2">User-defined Operators: the Idea</a></p></li>
<li><p><a class="reference internal" href="#user-defined-binary-operators" id="id3">User-defined Binary Operators</a></p></li>
<li><p><a class="reference internal" href="#user-defined-unary-operators" id="id4">User-defined Unary Operators</a></p></li>
<li><p><a class="reference internal" href="#kicking-the-tires" id="id5">Kicking the Tires</a></p></li>
<li><p><a class="reference internal" href="#full-code-listing" id="id6">Full Code Listing</a></p></li>
</ul>
</div>
<div class="section" id="chapter-6-introduction">
<h2><a class="toc-backref" href="#id1"><span class="section-number">6.1. </span>Chapter 6 Introduction</a><a class="headerlink" href="#chapter-6-introduction" title="Permalink to this headline">¶</a></h2>
<p>Welcome to Chapter 6 of the “<a class="reference external" href="index.html">Implementing a language with
LLVM</a>” tutorial. At this point in our tutorial, we now
have a fully functional language that is fairly minimal, but also
useful. There is still one big problem with it, however. Our language
doesn’t have many useful operators (like division, logical negation, or
even any comparisons besides less-than).</p>
<p>This chapter of the tutorial takes a wild digression into adding
user-defined operators to the simple and beautiful Kaleidoscope
language. This digression now gives us a simple and ugly language in
some ways, but also a powerful one at the same time. One of the great
things about creating your own language is that you get to decide what
is good or bad. In this tutorial we’ll assume that it is okay to use
this as a way to show some interesting parsing techniques.</p>
<p>At the end of this tutorial, we’ll run through an example Kaleidoscope
application that <a class="reference external" href="#kicking-the-tires">renders the Mandelbrot set</a>. This gives an
example of what you can build with Kaleidoscope and its feature set.</p>
</div>
<div class="section" id="user-defined-operators-the-idea">
<h2><a class="toc-backref" href="#id2"><span class="section-number">6.2. </span>User-defined Operators: the Idea</a><a class="headerlink" href="#user-defined-operators-the-idea" title="Permalink to this headline">¶</a></h2>
<p>The “operator overloading” that we will add to Kaleidoscope is more
general than languages like C++. In C++, you are only allowed to
redefine existing operators: you can’t programmatically change the
grammar, introduce new operators, change precedence levels, etc. In this
chapter, we will add this capability to Kaleidoscope, which will let the
user round out the set of operators that are supported.</p>
<p>The point of going into user-defined operators in a tutorial like this
is to show the power and flexibility of using a hand-written parser.
Thus far, the parser we have been implementing uses recursive descent
for most parts of the grammar and operator precedence parsing for the
expressions. See <a class="reference external" href="OCamlLangImpl2.html">Chapter 2</a> for details. Without
using operator precedence parsing, it would be very difficult to allow
the programmer to introduce new operators into the grammar: the grammar
is dynamically extensible as the JIT runs.</p>
<p>The two specific features we’ll add are programmable unary operators
(right now, Kaleidoscope has no unary operators at all) as well as
binary operators. An example of this is:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span># Logical unary not.
def unary!(v)
  if v then
    0
  else
    1;

# Define &gt; with the same precedence as &lt;.
def binary&gt; 10 (LHS RHS)
  RHS &lt; LHS;

# Binary &quot;logical or&quot;, (note that it does not &quot;short circuit&quot;)
def binary| 5 (LHS RHS)
  if LHS then
    1
  else if RHS then
    1
  else
    0;

# Define = with slightly lower precedence than relationals.
def binary= 9 (LHS RHS)
  !(LHS &lt; RHS | LHS &gt; RHS);
</pre></div>
</div>
<p>Many languages aspire to being able to implement their standard runtime
library in the language itself. In Kaleidoscope, we can implement
significant parts of the language in the library!</p>
<p>We will break down implementation of these features into two parts:
implementing support for user-defined binary operators and adding unary
operators.</p>
</div>
<div class="section" id="user-defined-binary-operators">
<h2><a class="toc-backref" href="#id3"><span class="section-number">6.3. </span>User-defined Binary Operators</a><a class="headerlink" href="#user-defined-binary-operators" title="Permalink to this headline">¶</a></h2>
<p>Adding support for user-defined binary operators is pretty simple with
our current framework. We’ll first add support for the unary/binary
keywords:</p>
<div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="k">type</span> <span class="n">token</span> <span class="o">=</span>
  <span class="o">...</span>
  <span class="c">(* operators *)</span>
  <span class="o">|</span> <span class="nc">Binary</span> <span class="o">|</span> <span class="nn">Unary</span>

<span class="p">...</span>

<span class="n">and</span> <span class="n">lex_ident</span> <span class="n">buffer</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="o">...</span>
      <span class="o">|</span> <span class="s2">&quot;for&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">For</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;in&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">In</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;binary&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Binary</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;unary&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Unary</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
</pre></div>
</div>
<p>This just adds lexer support for the unary and binary keywords, like we
did in <a class="reference external" href="OCamlLangImpl5.html#lexer-extensions-for-if-then-else">previous chapters</a>. One nice
thing about our current AST, is that we represent binary operators with
full generalisation by using their ASCII code as the opcode. For our
extended operators, we’ll use this same representation, so we don’t need
any new AST or parser support.</p>
<p>On the other hand, we have to be able to represent the definitions of
these new operators, in the “def binary| 5” part of the function
definition. In our grammar so far, the “name” for the function
definition is parsed as the “prototype” production and into the
<code class="docutils literal notranslate"><span class="pre">Ast.Prototype</span></code> AST node. To represent our new user-defined operators
as prototypes, we have to extend the <code class="docutils literal notranslate"><span class="pre">Ast.Prototype</span></code> AST node like
this:</p>
<div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(* proto - This type represents the &quot;prototype&quot; for a function, which captures</span>
<span class="c"> * its name, and its argument names (thus implicitly the number of arguments the</span>
<span class="c"> * function takes). *)</span>
<span class="k">type</span> <span class="n">proto</span> <span class="o">=</span>
  <span class="o">|</span> <span class="nc">Prototype</span> <span class="k">of</span> <span class="kt">string</span> <span class="o">*</span> <span class="kt">string</span> <span class="kt">array</span>
  <span class="o">|</span> <span class="nc">BinOpPrototype</span> <span class="k">of</span> <span class="kt">string</span> <span class="o">*</span> <span class="kt">string</span> <span class="kt">array</span> <span class="o">*</span> <span class="kt">int</span>
</pre></div>
</div>
<p>Basically, in addition to knowing a name for the prototype, we now keep
track of whether it was an operator, and if it was, what precedence
level the operator is at. The precedence is only used for binary
operators (as you’ll see below, it just doesn’t apply for unary
operators). Now that we have a way to represent the prototype for a
user-defined operator, we need to parse it:</p>
<div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(* prototype</span>
<span class="c"> *   ::= id &#39;(&#39; id* &#39;)&#39;</span>
<span class="c"> *   ::= binary LETTER number? (id, id)</span>
<span class="c"> *   ::= unary LETTER number? (id) *)</span>
<span class="k">let</span> <span class="n">parse_prototype</span> <span class="o">=</span>
  <span class="k">let</span> <span class="k">rec</span> <span class="n">parse_args</span> <span class="n">accumulator</span> <span class="o">=</span> <span class="n">parser</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Ident</span> <span class="n">id</span><span class="o">;</span> <span class="n">e</span><span class="o">=</span><span class="n">parse_args</span> <span class="o">(</span><span class="n">id</span><span class="o">::</span><span class="n">accumulator</span><span class="o">)</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">e</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">accumulator</span>
  <span class="k">in</span>
  <span class="k">let</span> <span class="n">parse_operator</span> <span class="o">=</span> <span class="n">parser</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Unary</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="s2">&quot;unary&quot;</span><span class="o">,</span> <span class="mi">1</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Binary</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="s2">&quot;binary&quot;</span><span class="o">,</span> <span class="mi">2</span>
  <span class="k">in</span>
  <span class="k">let</span> <span class="n">parse_binary_precedence</span> <span class="o">=</span> <span class="n">parser</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Number</span> <span class="n">n</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">int_of_float</span> <span class="n">n</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="mi">30</span>
  <span class="k">in</span>
  <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Ident</span> <span class="n">id</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;(&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;(&#39; in prototype&quot;</span><span class="o">;</span>
       <span class="n">args</span><span class="o">=</span><span class="n">parse_args</span> <span class="bp">[]</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;)&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;)&#39; in prototype&quot;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="c">(* success. *)</span>
      <span class="nn">Ast</span><span class="p">.</span><span class="nc">Prototype</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="nn">Array</span><span class="p">.</span><span class="n">of_list</span> <span class="o">(</span><span class="nn">List</span><span class="p">.</span><span class="n">rev</span> <span class="n">args</span><span class="o">))</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">(</span><span class="n">prefix</span><span class="o">,</span> <span class="n">kind</span><span class="o">)=</span><span class="n">parse_operator</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="n">op</span> <span class="o">??</span> <span class="s2">&quot;expected an operator&quot;</span><span class="o">;</span>
       <span class="c">(* Read the precedence if present. *)</span>
       <span class="n">binary_precedence</span><span class="o">=</span><span class="n">parse_binary_precedence</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;(&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;(&#39; in prototype&quot;</span><span class="o">;</span>
        <span class="n">args</span><span class="o">=</span><span class="n">parse_args</span> <span class="bp">[]</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;)&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;)&#39; in prototype&quot;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">name</span> <span class="o">=</span> <span class="n">prefix</span> <span class="o">^</span> <span class="o">(</span><span class="nn">String</span><span class="p">.</span><span class="n">make</span> <span class="mi">1</span> <span class="n">op</span><span class="o">)</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">args</span> <span class="o">=</span> <span class="nn">Array</span><span class="p">.</span><span class="n">of_list</span> <span class="o">(</span><span class="nn">List</span><span class="p">.</span><span class="n">rev</span> <span class="n">args</span><span class="o">)</span> <span class="k">in</span>

      <span class="c">(* Verify right number of arguments for operator. *)</span>
      <span class="k">if</span> <span class="nn">Array</span><span class="p">.</span><span class="n">length</span> <span class="n">args</span> <span class="o">!=</span> <span class="n">kind</span>
      <span class="k">then</span> <span class="k">raise</span> <span class="o">(</span><span class="nn">Stream</span><span class="p">.</span><span class="nc">Error</span> <span class="s2">&quot;invalid number of operands for operator&quot;</span><span class="o">)</span>
      <span class="k">else</span>
        <span class="k">if</span> <span class="n">kind</span> <span class="o">==</span> <span class="mi">1</span> <span class="k">then</span>
          <span class="nn">Ast</span><span class="p">.</span><span class="nc">Prototype</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">args</span><span class="o">)</span>
        <span class="k">else</span>
          <span class="nn">Ast</span><span class="p">.</span><span class="nc">BinOpPrototype</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">args</span><span class="o">,</span> <span class="n">binary_precedence</span><span class="o">)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">raise</span> <span class="o">(</span><span class="nn">Stream</span><span class="p">.</span><span class="nc">Error</span> <span class="s2">&quot;expected function name in prototype&quot;</span><span class="o">)</span>
</pre></div>
</div>
<p>This is all fairly straightforward parsing code, and we have already
seen a lot of similar code in the past. One interesting part about the
code above is the couple lines that set up <code class="docutils literal notranslate"><span class="pre">name</span></code> for binary
operators. This builds names like “binary&#64;” for a newly defined “&#64;”
operator. This then takes advantage of the fact that symbol names in the
LLVM symbol table are allowed to have any character in them, including
embedded nul characters.</p>
<p>The next interesting thing to add, is codegen support for these binary
operators. Given our current structure, this is a simple addition of a
default case for our existing binary operator node:</p>
<div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="k">let</span> <span class="n">codegen_expr</span> <span class="o">=</span> <span class="k">function</span>
  <span class="o">...</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Binary</span> <span class="o">(</span><span class="n">op</span><span class="o">,</span> <span class="n">lhs</span><span class="o">,</span> <span class="n">rhs</span><span class="o">)</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">lhs_val</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">lhs</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">rhs_val</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">rhs</span> <span class="k">in</span>
      <span class="k">begin</span>
        <span class="k">match</span> <span class="n">op</span> <span class="k">with</span>
        <span class="o">|</span> <span class="sc">&#39;+&#39;</span> <span class="o">-&gt;</span> <span class="n">build_add</span> <span class="n">lhs_val</span> <span class="n">rhs_val</span> <span class="s2">&quot;addtmp&quot;</span> <span class="n">builder</span>
        <span class="o">|</span> <span class="sc">&#39;-&#39;</span> <span class="o">-&gt;</span> <span class="n">build_sub</span> <span class="n">lhs_val</span> <span class="n">rhs_val</span> <span class="s2">&quot;subtmp&quot;</span> <span class="n">builder</span>
        <span class="o">|</span> <span class="sc">&#39;*&#39;</span> <span class="o">-&gt;</span> <span class="n">build_mul</span> <span class="n">lhs_val</span> <span class="n">rhs_val</span> <span class="s2">&quot;multmp&quot;</span> <span class="n">builder</span>
        <span class="o">|</span> <span class="sc">&#39;&lt;&#39;</span> <span class="o">-&gt;</span>
            <span class="c">(* Convert bool 0/1 to double 0.0 or 1.0 *)</span>
            <span class="k">let</span> <span class="n">i</span> <span class="o">=</span> <span class="n">build_fcmp</span> <span class="nn">Fcmp</span><span class="p">.</span><span class="nc">Ult</span> <span class="n">lhs_val</span> <span class="n">rhs_val</span> <span class="s2">&quot;cmptmp&quot;</span> <span class="n">builder</span> <span class="k">in</span>
            <span class="n">build_uitofp</span> <span class="n">i</span> <span class="n">double_type</span> <span class="s2">&quot;booltmp&quot;</span> <span class="n">builder</span>
        <span class="o">|</span> <span class="o">_</span> <span class="o">-&gt;</span>
            <span class="c">(* If it wasn&#39;t a builtin binary operator, it must be a user defined</span>
<span class="c">             * one. Emit a call to it. *)</span>
            <span class="k">let</span> <span class="n">callee</span> <span class="o">=</span> <span class="s2">&quot;binary&quot;</span> <span class="o">^</span> <span class="o">(</span><span class="nn">String</span><span class="p">.</span><span class="n">make</span> <span class="mi">1</span> <span class="n">op</span><span class="o">)</span> <span class="k">in</span>
            <span class="k">let</span> <span class="n">callee</span> <span class="o">=</span>
              <span class="k">match</span> <span class="n">lookup_function</span> <span class="n">callee</span> <span class="n">the_module</span> <span class="k">with</span>
              <span class="o">|</span> <span class="nc">Some</span> <span class="n">callee</span> <span class="o">-&gt;</span> <span class="n">callee</span>
              <span class="o">|</span> <span class="nc">None</span> <span class="o">-&gt;</span> <span class="k">raise</span> <span class="o">(</span><span class="nc">Error</span> <span class="s2">&quot;binary operator not found!&quot;</span><span class="o">)</span>
            <span class="k">in</span>
            <span class="n">build_call</span> <span class="n">callee</span> <span class="o">[|</span><span class="n">lhs_val</span><span class="o">;</span> <span class="n">rhs_val</span><span class="o">|]</span> <span class="s2">&quot;binop&quot;</span> <span class="n">builder</span>
      <span class="k">end</span>
</pre></div>
</div>
<p>As you can see above, the new code is actually really simple. It just
does a lookup for the appropriate operator in the symbol table and
generates a function call to it. Since user-defined operators are just
built as normal functions (because the “prototype” boils down to a
function with the right name) everything falls into place.</p>
<p>The final piece of code we are missing, is a bit of top level magic:</p>
<div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="k">let</span> <span class="n">codegen_func</span> <span class="n">the_fpm</span> <span class="o">=</span> <span class="k">function</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Function</span> <span class="o">(</span><span class="n">proto</span><span class="o">,</span> <span class="n">body</span><span class="o">)</span> <span class="o">-&gt;</span>
      <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">clear</span> <span class="n">named_values</span><span class="o">;</span>
      <span class="k">let</span> <span class="n">the_function</span> <span class="o">=</span> <span class="n">codegen_proto</span> <span class="n">proto</span> <span class="k">in</span>

      <span class="c">(* If this is an operator, install it. *)</span>
      <span class="k">begin</span> <span class="k">match</span> <span class="n">proto</span> <span class="k">with</span>
      <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">BinOpPrototype</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">args</span><span class="o">,</span> <span class="n">prec</span><span class="o">)</span> <span class="o">-&gt;</span>
          <span class="k">let</span> <span class="n">op</span> <span class="o">=</span> <span class="n">name</span><span class="o">.[</span><span class="nn">String</span><span class="p">.</span><span class="n">length</span> <span class="n">name</span> <span class="o">-</span> <span class="mi">1</span><span class="o">]</span> <span class="k">in</span>
          <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">add</span> <span class="nn">Parser</span><span class="p">.</span><span class="n">binop_precedence</span> <span class="n">op</span> <span class="n">prec</span><span class="o">;</span>
      <span class="o">|</span> <span class="o">_</span> <span class="o">-&gt;</span> <span class="bp">()</span>
      <span class="k">end</span><span class="o">;</span>

      <span class="c">(* Create a new basic block to start insertion into. *)</span>
      <span class="k">let</span> <span class="n">bb</span> <span class="o">=</span> <span class="n">append_block</span> <span class="n">context</span> <span class="s2">&quot;entry&quot;</span> <span class="n">the_function</span> <span class="k">in</span>
      <span class="n">position_at_end</span> <span class="n">bb</span> <span class="n">builder</span><span class="o">;</span>
      <span class="o">...</span>
</pre></div>
</div>
<p>Basically, before codegening a function, if it is a user-defined
operator, we register it in the precedence table. This allows the binary
operator parsing logic we already have in place to handle it. Since we
are working on a fully-general operator precedence parser, this is all
we need to do to “extend the grammar”.</p>
<p>Now we have useful user-defined binary operators. This builds a lot on
the previous framework we built for other operators. Adding unary
operators is a bit more challenging, because we don’t have any framework
for it yet - lets see what it takes.</p>
</div>
<div class="section" id="user-defined-unary-operators">
<h2><a class="toc-backref" href="#id4"><span class="section-number">6.4. </span>User-defined Unary Operators</a><a class="headerlink" href="#user-defined-unary-operators" title="Permalink to this headline">¶</a></h2>
<p>Since we don’t currently support unary operators in the Kaleidoscope
language, we’ll need to add everything to support them. Above, we added
simple support for the ‘unary’ keyword to the lexer. In addition to
that, we need an AST node:</p>
<div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="k">type</span> <span class="n">expr</span> <span class="o">=</span>
  <span class="o">...</span>
  <span class="c">(* variant for a unary operator. *)</span>
  <span class="o">|</span> <span class="nc">Unary</span> <span class="k">of</span> <span class="kt">char</span> <span class="o">*</span> <span class="n">expr</span>
  <span class="o">...</span>
</pre></div>
</div>
<p>This AST node is very simple and obvious by now. It directly mirrors the
binary operator AST node, except that it only has one child. With this,
we need to add the parsing logic. Parsing a unary operator is pretty
simple: we’ll add a new function to do it:</p>
<div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(* unary</span>
<span class="c"> *   ::= primary</span>
<span class="c"> *   ::= &#39;!&#39; unary *)</span>
<span class="ow">and</span> <span class="n">parse_unary</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="c">(* If this is a unary operator, read it. *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="n">op</span> <span class="k">when</span> <span class="n">op</span> <span class="o">!=</span> <span class="sc">&#39;(&#39;</span> <span class="o">&amp;&amp;</span> <span class="n">op</span> <span class="o">!=</span> <span class="sc">&#39;)&#39;</span><span class="o">;</span> <span class="n">operand</span><span class="o">=</span><span class="n">parse_expr</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="nn">Ast</span><span class="p">.</span><span class="nc">Unary</span> <span class="o">(</span><span class="n">op</span><span class="o">,</span> <span class="n">operand</span><span class="o">)</span>

  <span class="c">(* If the current token is not an operator, it must be a primary expr. *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">parse_primary</span> <span class="n">stream</span>
</pre></div>
</div>
<p>The grammar we add is pretty straightforward here. If we see a unary
operator when parsing a primary operator, we eat the operator as a
prefix and parse the remaining piece as another unary operator. This
allows us to handle multiple unary operators (e.g. “!!x”). Note that
unary operators can’t have ambiguous parses like binary operators can,
so there is no need for precedence information.</p>
<p>The problem with this function, is that we need to call ParseUnary from
somewhere. To do this, we change previous callers of ParsePrimary to
call <code class="docutils literal notranslate"><span class="pre">parse_unary</span></code> instead:</p>
<div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(* binoprhs</span>
<span class="c"> *   ::= (&#39;+&#39; primary)* *)</span>
<span class="ow">and</span> <span class="n">parse_bin_rhs</span> <span class="n">expr_prec</span> <span class="n">lhs</span> <span class="n">stream</span> <span class="o">=</span>
        <span class="o">...</span>
        <span class="c">(* Parse the unary expression after the binary operator. *)</span>
        <span class="k">let</span> <span class="n">rhs</span> <span class="o">=</span> <span class="n">parse_unary</span> <span class="n">stream</span> <span class="k">in</span>
        <span class="o">...</span>

<span class="o">...</span>

<span class="c">(* expression</span>
<span class="c"> *   ::= primary binoprhs *)</span>
<span class="ow">and</span> <span class="n">parse_expr</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="n">lhs</span><span class="o">=</span><span class="n">parse_unary</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">parse_bin_rhs</span> <span class="mi">0</span> <span class="n">lhs</span> <span class="n">stream</span>
</pre></div>
</div>
<p>With these two simple changes, we are now able to parse unary operators
and build the AST for them. Next up, we need to add parser support for
prototypes, to parse the unary operator prototype. We extend the binary
operator code above with:</p>
<div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(* prototype</span>
<span class="c"> *   ::= id &#39;(&#39; id* &#39;)&#39;</span>
<span class="c"> *   ::= binary LETTER number? (id, id)</span>
<span class="c"> *   ::= unary LETTER number? (id) *)</span>
<span class="k">let</span> <span class="n">parse_prototype</span> <span class="o">=</span>
  <span class="k">let</span> <span class="k">rec</span> <span class="n">parse_args</span> <span class="n">accumulator</span> <span class="o">=</span> <span class="n">parser</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Ident</span> <span class="n">id</span><span class="o">;</span> <span class="n">e</span><span class="o">=</span><span class="n">parse_args</span> <span class="o">(</span><span class="n">id</span><span class="o">::</span><span class="n">accumulator</span><span class="o">)</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">e</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">accumulator</span>
  <span class="k">in</span>
  <span class="k">let</span> <span class="n">parse_operator</span> <span class="o">=</span> <span class="n">parser</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Unary</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="s2">&quot;unary&quot;</span><span class="o">,</span> <span class="mi">1</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Binary</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="s2">&quot;binary&quot;</span><span class="o">,</span> <span class="mi">2</span>
  <span class="k">in</span>
  <span class="k">let</span> <span class="n">parse_binary_precedence</span> <span class="o">=</span> <span class="n">parser</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Number</span> <span class="n">n</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">int_of_float</span> <span class="n">n</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="mi">30</span>
  <span class="k">in</span>
  <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Ident</span> <span class="n">id</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;(&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;(&#39; in prototype&quot;</span><span class="o">;</span>
       <span class="n">args</span><span class="o">=</span><span class="n">parse_args</span> <span class="bp">[]</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;)&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;)&#39; in prototype&quot;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="c">(* success. *)</span>
      <span class="nn">Ast</span><span class="p">.</span><span class="nc">Prototype</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="nn">Array</span><span class="p">.</span><span class="n">of_list</span> <span class="o">(</span><span class="nn">List</span><span class="p">.</span><span class="n">rev</span> <span class="n">args</span><span class="o">))</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">(</span><span class="n">prefix</span><span class="o">,</span> <span class="n">kind</span><span class="o">)=</span><span class="n">parse_operator</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="n">op</span> <span class="o">??</span> <span class="s2">&quot;expected an operator&quot;</span><span class="o">;</span>
       <span class="c">(* Read the precedence if present. *)</span>
       <span class="n">binary_precedence</span><span class="o">=</span><span class="n">parse_binary_precedence</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;(&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;(&#39; in prototype&quot;</span><span class="o">;</span>
        <span class="n">args</span><span class="o">=</span><span class="n">parse_args</span> <span class="bp">[]</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;)&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;)&#39; in prototype&quot;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">name</span> <span class="o">=</span> <span class="n">prefix</span> <span class="o">^</span> <span class="o">(</span><span class="nn">String</span><span class="p">.</span><span class="n">make</span> <span class="mi">1</span> <span class="n">op</span><span class="o">)</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">args</span> <span class="o">=</span> <span class="nn">Array</span><span class="p">.</span><span class="n">of_list</span> <span class="o">(</span><span class="nn">List</span><span class="p">.</span><span class="n">rev</span> <span class="n">args</span><span class="o">)</span> <span class="k">in</span>

      <span class="c">(* Verify right number of arguments for operator. *)</span>
      <span class="k">if</span> <span class="nn">Array</span><span class="p">.</span><span class="n">length</span> <span class="n">args</span> <span class="o">!=</span> <span class="n">kind</span>
      <span class="k">then</span> <span class="k">raise</span> <span class="o">(</span><span class="nn">Stream</span><span class="p">.</span><span class="nc">Error</span> <span class="s2">&quot;invalid number of operands for operator&quot;</span><span class="o">)</span>
      <span class="k">else</span>
        <span class="k">if</span> <span class="n">kind</span> <span class="o">==</span> <span class="mi">1</span> <span class="k">then</span>
          <span class="nn">Ast</span><span class="p">.</span><span class="nc">Prototype</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">args</span><span class="o">)</span>
        <span class="k">else</span>
          <span class="nn">Ast</span><span class="p">.</span><span class="nc">BinOpPrototype</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">args</span><span class="o">,</span> <span class="n">binary_precedence</span><span class="o">)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">raise</span> <span class="o">(</span><span class="nn">Stream</span><span class="p">.</span><span class="nc">Error</span> <span class="s2">&quot;expected function name in prototype&quot;</span><span class="o">)</span>
</pre></div>
</div>
<p>As with binary operators, we name unary operators with a name that
includes the operator character. This assists us at code generation
time. Speaking of, the final piece we need to add is codegen support for
unary operators. It looks like this:</p>
<div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="k">let</span> <span class="k">rec</span> <span class="n">codegen_expr</span> <span class="o">=</span> <span class="k">function</span>
  <span class="o">...</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Unary</span> <span class="o">(</span><span class="n">op</span><span class="o">,</span> <span class="n">operand</span><span class="o">)</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">operand</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">operand</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">callee</span> <span class="o">=</span> <span class="s2">&quot;unary&quot;</span> <span class="o">^</span> <span class="o">(</span><span class="nn">String</span><span class="p">.</span><span class="n">make</span> <span class="mi">1</span> <span class="n">op</span><span class="o">)</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">callee</span> <span class="o">=</span>
        <span class="k">match</span> <span class="n">lookup_function</span> <span class="n">callee</span> <span class="n">the_module</span> <span class="k">with</span>
        <span class="o">|</span> <span class="nc">Some</span> <span class="n">callee</span> <span class="o">-&gt;</span> <span class="n">callee</span>
        <span class="o">|</span> <span class="nc">None</span> <span class="o">-&gt;</span> <span class="k">raise</span> <span class="o">(</span><span class="nc">Error</span> <span class="s2">&quot;unknown unary operator&quot;</span><span class="o">)</span>
      <span class="k">in</span>
      <span class="n">build_call</span> <span class="n">callee</span> <span class="o">[|</span><span class="n">operand</span><span class="o">|]</span> <span class="s2">&quot;unop&quot;</span> <span class="n">builder</span>
</pre></div>
</div>
<p>This code is similar to, but simpler than, the code for binary
operators. It is simpler primarily because it doesn’t need to handle any
predefined operators.</p>
</div>
<div class="section" id="kicking-the-tires">
<h2><a class="toc-backref" href="#id5"><span class="section-number">6.5. </span>Kicking the Tires</a><a class="headerlink" href="#kicking-the-tires" title="Permalink to this headline">¶</a></h2>
<p>It is somewhat hard to believe, but with a few simple extensions we’ve
covered in the last chapters, we have grown a real-ish language. With
this, we can do a lot of interesting things, including I/O, math, and a
bunch of other things. For example, we can now add a nice sequencing
operator (printd is defined to print out the specified value and a
newline):</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">ready</span><span class="o">&gt;</span> <span class="n">extern</span> <span class="n">printd</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
<span class="n">Read</span> <span class="n">extern</span><span class="p">:</span> <span class="n">declare</span> <span class="n">double</span> <span class="nd">@printd</span><span class="p">(</span><span class="n">double</span><span class="p">)</span>
<span class="n">ready</span><span class="o">&gt;</span> <span class="k">def</span> <span class="nf">binary</span> <span class="p">:</span> <span class="mi">1</span> <span class="p">(</span><span class="n">x</span> <span class="n">y</span><span class="p">)</span> <span class="mi">0</span><span class="p">;</span>  <span class="c1"># Low-precedence operator that ignores operands.</span>
<span class="o">..</span>
<span class="n">ready</span><span class="o">&gt;</span> <span class="n">printd</span><span class="p">(</span><span class="mi">123</span><span class="p">)</span> <span class="p">:</span> <span class="n">printd</span><span class="p">(</span><span class="mi">456</span><span class="p">)</span> <span class="p">:</span> <span class="n">printd</span><span class="p">(</span><span class="mi">789</span><span class="p">);</span>
<span class="mf">123.000000</span>
<span class="mf">456.000000</span>
<span class="mf">789.000000</span>
<span class="n">Evaluated</span> <span class="n">to</span> <span class="mf">0.000000</span>
</pre></div>
</div>
<p>We can also define a bunch of other “primitive” operations, such as:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span># Logical unary not.
def unary!(v)
  if v then
    0
  else
    1;

# Unary negate.
def unary-(v)
  0-v;

# Define &gt; with the same precedence as &lt;.
def binary&gt; 10 (LHS RHS)
  RHS &lt; LHS;

# Binary logical or, which does not short circuit.
def binary| 5 (LHS RHS)
  if LHS then
    1
  else if RHS then
    1
  else
    0;

# Binary logical and, which does not short circuit.
def binary&amp; 6 (LHS RHS)
  if !LHS then
    0
  else
    !!RHS;

# Define = with slightly lower precedence than relationals.
def binary = 9 (LHS RHS)
  !(LHS &lt; RHS | LHS &gt; RHS);
</pre></div>
</div>
<p>Given the previous if/then/else support, we can also define interesting
functions for I/O. For example, the following prints out a character
whose “density” reflects the value passed in: the lower the value, the
denser the character:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">ready</span><span class="o">&gt;</span>

<span class="n">extern</span> <span class="n">putchard</span><span class="p">(</span><span class="n">char</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">printdensity</span><span class="p">(</span><span class="n">d</span><span class="p">)</span>
  <span class="k">if</span> <span class="n">d</span> <span class="o">&gt;</span> <span class="mi">8</span> <span class="n">then</span>
    <span class="n">putchard</span><span class="p">(</span><span class="mi">32</span><span class="p">)</span>  <span class="c1"># &#39; &#39;</span>
  <span class="k">else</span> <span class="k">if</span> <span class="n">d</span> <span class="o">&gt;</span> <span class="mi">4</span> <span class="n">then</span>
    <span class="n">putchard</span><span class="p">(</span><span class="mi">46</span><span class="p">)</span>  <span class="c1"># &#39;.&#39;</span>
  <span class="k">else</span> <span class="k">if</span> <span class="n">d</span> <span class="o">&gt;</span> <span class="mi">2</span> <span class="n">then</span>
    <span class="n">putchard</span><span class="p">(</span><span class="mi">43</span><span class="p">)</span>  <span class="c1"># &#39;+&#39;</span>
  <span class="k">else</span>
    <span class="n">putchard</span><span class="p">(</span><span class="mi">42</span><span class="p">);</span> <span class="c1"># &#39;*&#39;</span>
<span class="o">...</span>
<span class="n">ready</span><span class="o">&gt;</span> <span class="n">printdensity</span><span class="p">(</span><span class="mi">1</span><span class="p">):</span> <span class="n">printdensity</span><span class="p">(</span><span class="mi">2</span><span class="p">):</span> <span class="n">printdensity</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span> <span class="p">:</span>
          <span class="n">printdensity</span><span class="p">(</span><span class="mi">4</span><span class="p">):</span> <span class="n">printdensity</span><span class="p">(</span><span class="mi">5</span><span class="p">):</span> <span class="n">printdensity</span><span class="p">(</span><span class="mi">9</span><span class="p">):</span> <span class="n">putchard</span><span class="p">(</span><span class="mi">10</span><span class="p">);</span>
<span class="o">*++..</span>
<span class="n">Evaluated</span> <span class="n">to</span> <span class="mf">0.000000</span>
</pre></div>
</div>
<p>Based on these simple primitive operations, we can start to define more
interesting things. For example, here’s a little function that solves
for the number of iterations it takes a function in the complex plane to
converge:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="c1"># determine whether the specific location diverges.</span>
<span class="c1"># Solve for z = z^2 + c in the complex plane.</span>
<span class="k">def</span> <span class="nf">mandelconverger</span><span class="p">(</span><span class="n">real</span> <span class="n">imag</span> <span class="n">iters</span> <span class="n">creal</span> <span class="n">cimag</span><span class="p">)</span>
  <span class="k">if</span> <span class="n">iters</span> <span class="o">&gt;</span> <span class="mi">255</span> <span class="o">|</span> <span class="p">(</span><span class="n">real</span><span class="o">*</span><span class="n">real</span> <span class="o">+</span> <span class="n">imag</span><span class="o">*</span><span class="n">imag</span> <span class="o">&gt;</span> <span class="mi">4</span><span class="p">)</span> <span class="n">then</span>
    <span class="n">iters</span>
  <span class="k">else</span>
    <span class="n">mandelconverger</span><span class="p">(</span><span class="n">real</span><span class="o">*</span><span class="n">real</span> <span class="o">-</span> <span class="n">imag</span><span class="o">*</span><span class="n">imag</span> <span class="o">+</span> <span class="n">creal</span><span class="p">,</span>
                    <span class="mi">2</span><span class="o">*</span><span class="n">real</span><span class="o">*</span><span class="n">imag</span> <span class="o">+</span> <span class="n">cimag</span><span class="p">,</span>
                    <span class="n">iters</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">creal</span><span class="p">,</span> <span class="n">cimag</span><span class="p">);</span>

<span class="c1"># return the number of iterations required for the iteration to escape</span>
<span class="k">def</span> <span class="nf">mandelconverge</span><span class="p">(</span><span class="n">real</span> <span class="n">imag</span><span class="p">)</span>
  <span class="n">mandelconverger</span><span class="p">(</span><span class="n">real</span><span class="p">,</span> <span class="n">imag</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">real</span><span class="p">,</span> <span class="n">imag</span><span class="p">);</span>
</pre></div>
</div>
<p>This “z = z<sup>2</sup> + c” function is a beautiful little creature
that is the basis for computation of the <a class="reference external" href="http://en.wikipedia.org/wiki/Mandelbrot_set">Mandelbrot
Set</a>. Our
<code class="docutils literal notranslate"><span class="pre">mandelconverge</span></code> function returns the number of iterations that it
takes for a complex orbit to escape, saturating to 255. This is not a
very useful function by itself, but if you plot its value over a
two-dimensional plane, you can see the Mandelbrot set. Given that we are
limited to using putchard here, our amazing graphical output is limited,
but we can whip together something using the density plotter above:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="c1"># compute and plot the mandelbrot set with the specified 2 dimensional range</span>
<span class="c1"># info.</span>
<span class="k">def</span> <span class="nf">mandelhelp</span><span class="p">(</span><span class="n">xmin</span> <span class="n">xmax</span> <span class="n">xstep</span>   <span class="n">ymin</span> <span class="n">ymax</span> <span class="n">ystep</span><span class="p">)</span>
  <span class="k">for</span> <span class="n">y</span> <span class="o">=</span> <span class="n">ymin</span><span class="p">,</span> <span class="n">y</span> <span class="o">&lt;</span> <span class="n">ymax</span><span class="p">,</span> <span class="n">ystep</span> <span class="ow">in</span> <span class="p">(</span>
    <span class="p">(</span><span class="k">for</span> <span class="n">x</span> <span class="o">=</span> <span class="n">xmin</span><span class="p">,</span> <span class="n">x</span> <span class="o">&lt;</span> <span class="n">xmax</span><span class="p">,</span> <span class="n">xstep</span> <span class="ow">in</span>
       <span class="n">printdensity</span><span class="p">(</span><span class="n">mandelconverge</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">)))</span>
    <span class="p">:</span> <span class="n">putchard</span><span class="p">(</span><span class="mi">10</span><span class="p">)</span>
  <span class="p">)</span>

<span class="c1"># mandel - This is a convenient helper function for plotting the mandelbrot set</span>
<span class="c1"># from the specified position with the specified Magnification.</span>
<span class="k">def</span> <span class="nf">mandel</span><span class="p">(</span><span class="n">realstart</span> <span class="n">imagstart</span> <span class="n">realmag</span> <span class="n">imagmag</span><span class="p">)</span>
  <span class="n">mandelhelp</span><span class="p">(</span><span class="n">realstart</span><span class="p">,</span> <span class="n">realstart</span><span class="o">+</span><span class="n">realmag</span><span class="o">*</span><span class="mi">78</span><span class="p">,</span> <span class="n">realmag</span><span class="p">,</span>
             <span class="n">imagstart</span><span class="p">,</span> <span class="n">imagstart</span><span class="o">+</span><span class="n">imagmag</span><span class="o">*</span><span class="mi">40</span><span class="p">,</span> <span class="n">imagmag</span><span class="p">);</span>
</pre></div>
</div>
<p>Given this, we can try plotting out the mandelbrot set! Lets try it out:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">ready</span><span class="o">&gt;</span> <span class="n">mandel</span><span class="p">(</span><span class="o">-</span><span class="mf">2.3</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.3</span><span class="p">,</span> <span class="mf">0.05</span><span class="p">,</span> <span class="mf">0.07</span><span class="p">);</span>
<span class="o">*******************************+++++++++++*************************************</span>
<span class="o">*************************+++++++++++++++++++++++*******************************</span>
<span class="o">**********************+++++++++++++++++++++++++++++****************************</span>
<span class="o">*******************+++++++++++++++++++++..</span> <span class="o">...++++++++*************************</span>
<span class="o">*****************++++++++++++++++++++++....</span> <span class="o">...+++++++++***********************</span>
<span class="o">***************+++++++++++++++++++++++.....</span>   <span class="o">...+++++++++*********************</span>
<span class="o">**************+++++++++++++++++++++++....</span>     <span class="o">....+++++++++********************</span>
<span class="o">*************++++++++++++++++++++++......</span>      <span class="o">.....++++++++*******************</span>
<span class="o">************+++++++++++++++++++++.......</span>       <span class="o">.......+++++++******************</span>
<span class="o">***********+++++++++++++++++++....</span>                <span class="o">...</span> <span class="o">.+++++++*****************</span>
<span class="o">**********+++++++++++++++++.......</span>                     <span class="o">.+++++++****************</span>
<span class="o">*********++++++++++++++...........</span>                    <span class="o">...+++++++***************</span>
<span class="o">********++++++++++++............</span>                      <span class="o">...++++++++**************</span>
<span class="o">********++++++++++...</span> <span class="o">..........</span>                        <span class="o">.++++++++**************</span>
<span class="o">*******+++++++++.....</span>                                   <span class="o">.+++++++++*************</span>
<span class="o">*******++++++++......</span>                                  <span class="o">..+++++++++*************</span>
<span class="o">*******++++++.......</span>                                   <span class="o">..+++++++++*************</span>
<span class="o">*******+++++......</span>                                     <span class="o">..+++++++++*************</span>
<span class="o">*******....</span> <span class="o">....</span>                                      <span class="o">...+++++++++*************</span>
<span class="o">*******....</span> <span class="o">.</span>                                         <span class="o">...+++++++++*************</span>
<span class="o">*******+++++......</span>                                    <span class="o">...+++++++++*************</span>
<span class="o">*******++++++.......</span>                                   <span class="o">..+++++++++*************</span>
<span class="o">*******++++++++......</span>                                   <span class="o">.+++++++++*************</span>
<span class="o">*******+++++++++.....</span>                                  <span class="o">..+++++++++*************</span>
<span class="o">********++++++++++...</span> <span class="o">..........</span>                        <span class="o">.++++++++**************</span>
<span class="o">********++++++++++++............</span>                      <span class="o">...++++++++**************</span>
<span class="o">*********++++++++++++++..........</span>                     <span class="o">...+++++++***************</span>
<span class="o">**********++++++++++++++++........</span>                     <span class="o">.+++++++****************</span>
<span class="o">**********++++++++++++++++++++....</span>                <span class="o">...</span> <span class="o">..+++++++****************</span>
<span class="o">***********++++++++++++++++++++++.......</span>       <span class="o">.......++++++++*****************</span>
<span class="o">************+++++++++++++++++++++++......</span>      <span class="o">......++++++++******************</span>
<span class="o">**************+++++++++++++++++++++++....</span>      <span class="o">....++++++++********************</span>
<span class="o">***************+++++++++++++++++++++++.....</span>   <span class="o">...+++++++++*********************</span>
<span class="o">*****************++++++++++++++++++++++....</span>  <span class="o">...++++++++***********************</span>
<span class="o">*******************+++++++++++++++++++++......++++++++*************************</span>
<span class="o">*********************++++++++++++++++++++++.++++++++***************************</span>
<span class="o">*************************+++++++++++++++++++++++*******************************</span>
<span class="o">******************************+++++++++++++************************************</span>
<span class="o">*******************************************************************************</span>
<span class="o">*******************************************************************************</span>
<span class="o">*******************************************************************************</span>
<span class="n">Evaluated</span> <span class="n">to</span> <span class="mf">0.000000</span>
<span class="n">ready</span><span class="o">&gt;</span> <span class="n">mandel</span><span class="p">(</span><span class="o">-</span><span class="mi">2</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mf">0.02</span><span class="p">,</span> <span class="mf">0.04</span><span class="p">);</span>
<span class="o">**************************+++++++++++++++++++++++++++++++++++++++++++++++++++++</span>
<span class="o">***********************++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span>
<span class="o">*********************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.</span>
<span class="o">*******************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++...</span>
<span class="o">*****************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.....</span>
<span class="o">***************++++++++++++++++++++++++++++++++++++++++++++++++++++++++........</span>
<span class="o">**************++++++++++++++++++++++++++++++++++++++++++++++++++++++...........</span>
<span class="o">************+++++++++++++++++++++++++++++++++++++++++++++++++++++..............</span>
<span class="o">***********++++++++++++++++++++++++++++++++++++++++++++++++++........</span>        <span class="o">.</span>
<span class="o">**********++++++++++++++++++++++++++++++++++++++++++++++.............</span>
<span class="o">********+++++++++++++++++++++++++++++++++++++++++++..................</span>
<span class="o">*******+++++++++++++++++++++++++++++++++++++++.......................</span>
<span class="o">******+++++++++++++++++++++++++++++++++++...........................</span>
<span class="o">*****++++++++++++++++++++++++++++++++............................</span>
<span class="o">*****++++++++++++++++++++++++++++...............................</span>
<span class="o">****++++++++++++++++++++++++++......</span>   <span class="o">.........................</span>
<span class="o">***++++++++++++++++++++++++.........</span>     <span class="o">......</span>    <span class="o">...........</span>
<span class="o">***++++++++++++++++++++++............</span>
<span class="o">**+++++++++++++++++++++..............</span>
<span class="o">**+++++++++++++++++++................</span>
<span class="o">*++++++++++++++++++.................</span>
<span class="o">*++++++++++++++++............</span> <span class="o">...</span>
<span class="o">*++++++++++++++..............</span>
<span class="o">*+++....++++................</span>
<span class="o">*..........</span>  <span class="o">...........</span>
<span class="o">*</span>
<span class="o">*..........</span>  <span class="o">...........</span>
<span class="o">*+++....++++................</span>
<span class="o">*++++++++++++++..............</span>
<span class="o">*++++++++++++++++............</span> <span class="o">...</span>
<span class="o">*++++++++++++++++++.................</span>
<span class="o">**+++++++++++++++++++................</span>
<span class="o">**+++++++++++++++++++++..............</span>
<span class="o">***++++++++++++++++++++++............</span>
<span class="o">***++++++++++++++++++++++++.........</span>     <span class="o">......</span>    <span class="o">...........</span>
<span class="o">****++++++++++++++++++++++++++......</span>   <span class="o">.........................</span>
<span class="o">*****++++++++++++++++++++++++++++...............................</span>
<span class="o">*****++++++++++++++++++++++++++++++++............................</span>
<span class="o">******+++++++++++++++++++++++++++++++++++...........................</span>
<span class="o">*******+++++++++++++++++++++++++++++++++++++++.......................</span>
<span class="o">********+++++++++++++++++++++++++++++++++++++++++++..................</span>
<span class="n">Evaluated</span> <span class="n">to</span> <span class="mf">0.000000</span>
<span class="n">ready</span><span class="o">&gt;</span> <span class="n">mandel</span><span class="p">(</span><span class="o">-</span><span class="mf">0.9</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.4</span><span class="p">,</span> <span class="mf">0.02</span><span class="p">,</span> <span class="mf">0.03</span><span class="p">);</span>
<span class="o">*******************************************************************************</span>
<span class="o">*******************************************************************************</span>
<span class="o">*******************************************************************************</span>
<span class="o">**********+++++++++++++++++++++************************************************</span>
<span class="o">*+++++++++++++++++++++++++++++++++++++++***************************************</span>
<span class="o">+++++++++++++++++++++++++++++++++++++++++++++**********************************</span>
<span class="o">++++++++++++++++++++++++++++++++++++++++++++++++++*****************************</span>
<span class="o">++++++++++++++++++++++++++++++++++++++++++++++++++++++*************************</span>
<span class="o">+++++++++++++++++++++++++++++++++++++++++++++++++++++++++**********************</span>
<span class="o">+++++++++++++++++++++++++++++++++.........++++++++++++++++++*******************</span>
<span class="o">+++++++++++++++++++++++++++++++....</span>   <span class="o">......+++++++++++++++++++****************</span>
<span class="o">+++++++++++++++++++++++++++++.......</span>  <span class="o">........+++++++++++++++++++**************</span>
<span class="o">++++++++++++++++++++++++++++........</span>   <span class="o">........++++++++++++++++++++************</span>
<span class="o">+++++++++++++++++++++++++++.........</span>     <span class="o">..</span>  <span class="o">...+++++++++++++++++++++**********</span>
<span class="o">++++++++++++++++++++++++++...........</span>        <span class="o">....++++++++++++++++++++++********</span>
<span class="o">++++++++++++++++++++++++.............</span>       <span class="o">.......++++++++++++++++++++++******</span>
<span class="o">+++++++++++++++++++++++.............</span>        <span class="o">........+++++++++++++++++++++++****</span>
<span class="o">++++++++++++++++++++++...........</span>           <span class="o">..........++++++++++++++++++++++***</span>
<span class="o">++++++++++++++++++++...........</span>                <span class="o">.........++++++++++++++++++++++*</span>
<span class="o">++++++++++++++++++............</span>                  <span class="o">...........++++++++++++++++++++</span>
<span class="o">++++++++++++++++...............</span>                 <span class="o">.............++++++++++++++++++</span>
<span class="o">++++++++++++++.................</span>                 <span class="o">...............++++++++++++++++</span>
<span class="o">++++++++++++..................</span>                  <span class="o">.................++++++++++++++</span>
<span class="o">+++++++++..................</span>                      <span class="o">.................+++++++++++++</span>
<span class="o">++++++........</span>        <span class="o">.</span>                               <span class="o">.........</span>  <span class="o">..++++++++++++</span>
<span class="o">++............</span>                                         <span class="o">......</span>    <span class="o">....++++++++++</span>
<span class="o">..............</span>                                                    <span class="o">...++++++++++</span>
<span class="o">..............</span>                                                    <span class="o">....+++++++++</span>
<span class="o">..............</span>                                                    <span class="o">.....++++++++</span>
<span class="o">.............</span>                                                    <span class="o">......++++++++</span>
<span class="o">...........</span>                                                     <span class="o">.......++++++++</span>
<span class="o">.........</span>                                                       <span class="o">........+++++++</span>
<span class="o">.........</span>                                                       <span class="o">........+++++++</span>
<span class="o">.........</span>                                                           <span class="o">....+++++++</span>
<span class="o">........</span>                                                             <span class="o">...+++++++</span>
<span class="o">.......</span>                                                              <span class="o">...+++++++</span>
                                                                    <span class="o">....+++++++</span>
                                                                   <span class="o">.....+++++++</span>
                                                                    <span class="o">....+++++++</span>
                                                                    <span class="o">....+++++++</span>
                                                                    <span class="o">....+++++++</span>
<span class="n">Evaluated</span> <span class="n">to</span> <span class="mf">0.000000</span>
<span class="n">ready</span><span class="o">&gt;</span> <span class="o">^</span><span class="n">D</span>
</pre></div>
</div>
<p>At this point, you may be starting to realize that Kaleidoscope is a
real and powerful language. It may not be self-similar :), but it can be
used to plot things that are!</p>
<p>With this, we conclude the “adding user-defined operators” chapter of
the tutorial. We have successfully augmented our language, adding the
ability to extend the language in the library, and we have shown how
this can be used to build a simple but interesting end-user application
in Kaleidoscope. At this point, Kaleidoscope can build a variety of
applications that are functional and can call functions with
side-effects, but it can’t actually define and mutate a variable itself.</p>
<p>Strikingly, variable mutation is an important feature of some languages,
and it is not at all obvious how to <a class="reference external" href="OCamlLangImpl7.html">add support for mutable
variables</a> without having to add an “SSA
construction” phase to your front-end. In the next chapter, we will
describe how you can add variable mutation without building SSA in your
front-end.</p>
</div>
<div class="section" id="full-code-listing">
<h2><a class="toc-backref" href="#id6"><span class="section-number">6.6. </span>Full Code Listing</a><a class="headerlink" href="#full-code-listing" title="Permalink to this headline">¶</a></h2>
<p>Here is the complete code listing for our running example, enhanced with
the if/then/else and for expressions.. To build this example, use:</p>
<div class="highlight-bash notranslate"><div class="highlight"><pre><span></span><span class="c1"># Compile</span>
ocamlbuild toy.byte
<span class="c1"># Run</span>
./toy.byte
</pre></div>
</div>
<p>Here is the code:</p>
<dl>
<dt>_tags:</dt><dd><div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">&lt;</span><span class="p">{</span><span class="n">lexer</span><span class="p">,</span><span class="n">parser</span><span class="p">}</span><span class="o">.</span><span class="n">ml</span><span class="o">&gt;</span><span class="p">:</span> <span class="n">use_camlp4</span><span class="p">,</span> <span class="n">pp</span><span class="p">(</span><span class="n">camlp4of</span><span class="p">)</span>
<span class="o">&lt;*.</span><span class="p">{</span><span class="n">byte</span><span class="p">,</span><span class="n">native</span><span class="p">}</span><span class="o">&gt;</span><span class="p">:</span> <span class="n">g</span><span class="o">++</span><span class="p">,</span> <span class="n">use_llvm</span><span class="p">,</span> <span class="n">use_llvm_analysis</span>
<span class="o">&lt;*.</span><span class="p">{</span><span class="n">byte</span><span class="p">,</span><span class="n">native</span><span class="p">}</span><span class="o">&gt;</span><span class="p">:</span> <span class="n">use_llvm_executionengine</span><span class="p">,</span> <span class="n">use_llvm_target</span>
<span class="o">&lt;*.</span><span class="p">{</span><span class="n">byte</span><span class="p">,</span><span class="n">native</span><span class="p">}</span><span class="o">&gt;</span><span class="p">:</span> <span class="n">use_llvm_scalar_opts</span><span class="p">,</span> <span class="n">use_bindings</span>
</pre></div>
</div>
</dd>
<dt>myocamlbuild.ml:</dt><dd><div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="k">open</span> <span class="nc">Ocamlbuild_plugin</span><span class="o">;;</span>

<span class="n">ocaml_lib</span> <span class="o">~</span><span class="n">extern</span><span class="o">:</span><span class="bp">true</span> <span class="s2">&quot;llvm&quot;</span><span class="o">;;</span>
<span class="n">ocaml_lib</span> <span class="o">~</span><span class="n">extern</span><span class="o">:</span><span class="bp">true</span> <span class="s2">&quot;llvm_analysis&quot;</span><span class="o">;;</span>
<span class="n">ocaml_lib</span> <span class="o">~</span><span class="n">extern</span><span class="o">:</span><span class="bp">true</span> <span class="s2">&quot;llvm_executionengine&quot;</span><span class="o">;;</span>
<span class="n">ocaml_lib</span> <span class="o">~</span><span class="n">extern</span><span class="o">:</span><span class="bp">true</span> <span class="s2">&quot;llvm_target&quot;</span><span class="o">;;</span>
<span class="n">ocaml_lib</span> <span class="o">~</span><span class="n">extern</span><span class="o">:</span><span class="bp">true</span> <span class="s2">&quot;llvm_scalar_opts&quot;</span><span class="o">;;</span>

<span class="n">flag</span> <span class="o">[</span><span class="s2">&quot;link&quot;</span><span class="o">;</span> <span class="s2">&quot;ocaml&quot;</span><span class="o">;</span> <span class="s2">&quot;g++&quot;</span><span class="o">]</span> <span class="o">(</span><span class="nc">S</span><span class="o">[</span><span class="nc">A</span><span class="s2">&quot;-cc&quot;</span><span class="o">;</span> <span class="nc">A</span><span class="s2">&quot;g++&quot;</span><span class="o">;</span> <span class="nc">A</span><span class="s2">&quot;-cclib&quot;</span><span class="o">;</span> <span class="nc">A</span><span class="s2">&quot;-rdynamic&quot;</span><span class="o">]);;</span>
<span class="n">dep</span> <span class="o">[</span><span class="s2">&quot;link&quot;</span><span class="o">;</span> <span class="s2">&quot;ocaml&quot;</span><span class="o">;</span> <span class="s2">&quot;use_bindings&quot;</span><span class="o">]</span> <span class="o">[</span><span class="s2">&quot;bindings.o&quot;</span><span class="o">];;</span>
</pre></div>
</div>
</dd>
<dt>token.ml:</dt><dd><div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(*===----------------------------------------------------------------------===</span>
<span class="c"> * Lexer Tokens</span>
<span class="c"> *===----------------------------------------------------------------------===*)</span>

<span class="c">(* The lexer returns these &#39;Kwd&#39; if it is an unknown character, otherwise one of</span>
<span class="c"> * these others for known things. *)</span>
<span class="k">type</span> <span class="n">token</span> <span class="o">=</span>
  <span class="c">(* commands *)</span>
  <span class="o">|</span> <span class="nc">Def</span> <span class="o">|</span> <span class="nc">Extern</span>

  <span class="c">(* primary *)</span>
  <span class="o">|</span> <span class="nc">Ident</span> <span class="k">of</span> <span class="kt">string</span> <span class="o">|</span> <span class="nc">Number</span> <span class="k">of</span> <span class="kt">float</span>

  <span class="c">(* unknown *)</span>
  <span class="o">|</span> <span class="nc">Kwd</span> <span class="k">of</span> <span class="kt">char</span>

  <span class="c">(* control *)</span>
  <span class="o">|</span> <span class="nc">If</span> <span class="o">|</span> <span class="nc">Then</span> <span class="o">|</span> <span class="nc">Else</span>
  <span class="o">|</span> <span class="nc">For</span> <span class="o">|</span> <span class="nc">In</span>

  <span class="c">(* operators *)</span>
  <span class="o">|</span> <span class="nc">Binary</span> <span class="o">|</span> <span class="nc">Unary</span>
</pre></div>
</div>
</dd>
<dt>lexer.ml:</dt><dd><div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(*===----------------------------------------------------------------------===</span>
<span class="c"> * Lexer</span>
<span class="c"> *===----------------------------------------------------------------------===*)</span>

<span class="k">let</span> <span class="k">rec</span> <span class="n">lex</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="c">(* Skip any whitespace. *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span> <span class="o">(</span><span class="sc">&#39; &#39;</span> <span class="o">|</span> <span class="sc">&#39;\n&#39;</span> <span class="o">|</span> <span class="sc">&#39;\r&#39;</span> <span class="o">|</span> <span class="sc">&#39;\t&#39;</span><span class="o">);</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">lex</span> <span class="n">stream</span>

  <span class="c">(* identifier: [a-zA-Z][a-zA-Z0-9] *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span> <span class="o">(</span><span class="sc">&#39;A&#39;</span> <span class="o">..</span> <span class="sc">&#39;Z&#39;</span> <span class="o">|</span> <span class="sc">&#39;a&#39;</span> <span class="o">..</span> <span class="sc">&#39;z&#39;</span> <span class="k">as</span> <span class="n">c</span><span class="o">);</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">buffer</span> <span class="o">=</span> <span class="nn">Buffer</span><span class="p">.</span><span class="n">create</span> <span class="mi">1</span> <span class="k">in</span>
      <span class="nn">Buffer</span><span class="p">.</span><span class="n">add_char</span> <span class="n">buffer</span> <span class="n">c</span><span class="o">;</span>
      <span class="n">lex_ident</span> <span class="n">buffer</span> <span class="n">stream</span>

  <span class="c">(* number: [0-9.]+ *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span> <span class="o">(</span><span class="sc">&#39;0&#39;</span> <span class="o">..</span> <span class="sc">&#39;9&#39;</span> <span class="k">as</span> <span class="n">c</span><span class="o">);</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">buffer</span> <span class="o">=</span> <span class="nn">Buffer</span><span class="p">.</span><span class="n">create</span> <span class="mi">1</span> <span class="k">in</span>
      <span class="nn">Buffer</span><span class="p">.</span><span class="n">add_char</span> <span class="n">buffer</span> <span class="n">c</span><span class="o">;</span>
      <span class="n">lex_number</span> <span class="n">buffer</span> <span class="n">stream</span>

  <span class="c">(* Comment until end of line. *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span> <span class="o">(</span><span class="sc">&#39;#&#39;</span><span class="o">);</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="n">lex_comment</span> <span class="n">stream</span>

  <span class="c">(* Otherwise, just return the character as its ascii value. *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="n">c</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="n">c</span><span class="o">;</span> <span class="n">lex</span> <span class="n">stream</span> <span class="o">&gt;]</span>

  <span class="c">(* end of stream. *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span>

<span class="ow">and</span> <span class="n">lex_number</span> <span class="n">buffer</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span> <span class="o">(</span><span class="sc">&#39;0&#39;</span> <span class="o">..</span> <span class="sc">&#39;9&#39;</span> <span class="o">|</span> <span class="sc">&#39;.&#39;</span> <span class="k">as</span> <span class="n">c</span><span class="o">);</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="nn">Buffer</span><span class="p">.</span><span class="n">add_char</span> <span class="n">buffer</span> <span class="n">c</span><span class="o">;</span>
      <span class="n">lex_number</span> <span class="n">buffer</span> <span class="n">stream</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="n">stream</span><span class="o">=</span><span class="n">lex</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Number</span> <span class="o">(</span><span class="n">float_of_string</span> <span class="o">(</span><span class="nn">Buffer</span><span class="p">.</span><span class="n">contents</span> <span class="n">buffer</span><span class="o">));</span> <span class="n">stream</span> <span class="o">&gt;]</span>

<span class="ow">and</span> <span class="n">lex_ident</span> <span class="n">buffer</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span> <span class="o">(</span><span class="sc">&#39;A&#39;</span> <span class="o">..</span> <span class="sc">&#39;Z&#39;</span> <span class="o">|</span> <span class="sc">&#39;a&#39;</span> <span class="o">..</span> <span class="sc">&#39;z&#39;</span> <span class="o">|</span> <span class="sc">&#39;0&#39;</span> <span class="o">..</span> <span class="sc">&#39;9&#39;</span> <span class="k">as</span> <span class="n">c</span><span class="o">);</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="nn">Buffer</span><span class="p">.</span><span class="n">add_char</span> <span class="n">buffer</span> <span class="n">c</span><span class="o">;</span>
      <span class="n">lex_ident</span> <span class="n">buffer</span> <span class="n">stream</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="n">stream</span><span class="o">=</span><span class="n">lex</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">match</span> <span class="nn">Buffer</span><span class="p">.</span><span class="n">contents</span> <span class="n">buffer</span> <span class="k">with</span>
      <span class="o">|</span> <span class="s2">&quot;def&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Def</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;extern&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Extern</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;if&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">If</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;then&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Then</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;else&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Else</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;for&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">For</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;in&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">In</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;binary&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Binary</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="s2">&quot;unary&quot;</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Unary</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>
      <span class="o">|</span> <span class="n">id</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Ident</span> <span class="n">id</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span>

<span class="ow">and</span> <span class="n">lex_comment</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span> <span class="o">(</span><span class="sc">&#39;\n&#39;</span><span class="o">);</span> <span class="n">stream</span><span class="o">=</span><span class="n">lex</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">stream</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="n">c</span><span class="o">;</span> <span class="n">e</span><span class="o">=</span><span class="n">lex_comment</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">e</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span>
</pre></div>
</div>
</dd>
<dt>ast.ml:</dt><dd><div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(*===----------------------------------------------------------------------===</span>
<span class="c"> * Abstract Syntax Tree (aka Parse Tree)</span>
<span class="c"> *===----------------------------------------------------------------------===*)</span>

<span class="c">(* expr - Base type for all expression nodes. *)</span>
<span class="k">type</span> <span class="n">expr</span> <span class="o">=</span>
  <span class="c">(* variant for numeric literals like &quot;1.0&quot;. *)</span>
  <span class="o">|</span> <span class="nc">Number</span> <span class="k">of</span> <span class="kt">float</span>

  <span class="c">(* variant for referencing a variable, like &quot;a&quot;. *)</span>
  <span class="o">|</span> <span class="nc">Variable</span> <span class="k">of</span> <span class="kt">string</span>

  <span class="c">(* variant for a unary operator. *)</span>
  <span class="o">|</span> <span class="nc">Unary</span> <span class="k">of</span> <span class="kt">char</span> <span class="o">*</span> <span class="n">expr</span>

  <span class="c">(* variant for a binary operator. *)</span>
  <span class="o">|</span> <span class="nc">Binary</span> <span class="k">of</span> <span class="kt">char</span> <span class="o">*</span> <span class="n">expr</span> <span class="o">*</span> <span class="n">expr</span>

  <span class="c">(* variant for function calls. *)</span>
  <span class="o">|</span> <span class="nc">Call</span> <span class="k">of</span> <span class="kt">string</span> <span class="o">*</span> <span class="n">expr</span> <span class="kt">array</span>

  <span class="c">(* variant for if/then/else. *)</span>
  <span class="o">|</span> <span class="nc">If</span> <span class="k">of</span> <span class="n">expr</span> <span class="o">*</span> <span class="n">expr</span> <span class="o">*</span> <span class="n">expr</span>

  <span class="c">(* variant for for/in. *)</span>
  <span class="o">|</span> <span class="nc">For</span> <span class="k">of</span> <span class="kt">string</span> <span class="o">*</span> <span class="n">expr</span> <span class="o">*</span> <span class="n">expr</span> <span class="o">*</span> <span class="n">expr</span> <span class="n">option</span> <span class="o">*</span> <span class="n">expr</span>

<span class="c">(* proto - This type represents the &quot;prototype&quot; for a function, which captures</span>
<span class="c"> * its name, and its argument names (thus implicitly the number of arguments the</span>
<span class="c"> * function takes). *)</span>
<span class="k">type</span> <span class="n">proto</span> <span class="o">=</span>
  <span class="o">|</span> <span class="nc">Prototype</span> <span class="k">of</span> <span class="kt">string</span> <span class="o">*</span> <span class="kt">string</span> <span class="kt">array</span>
  <span class="o">|</span> <span class="nc">BinOpPrototype</span> <span class="k">of</span> <span class="kt">string</span> <span class="o">*</span> <span class="kt">string</span> <span class="kt">array</span> <span class="o">*</span> <span class="kt">int</span>

<span class="c">(* func - This type represents a function definition itself. *)</span>
<span class="k">type</span> <span class="n">func</span> <span class="o">=</span> <span class="nc">Function</span> <span class="k">of</span> <span class="n">proto</span> <span class="o">*</span> <span class="n">expr</span>
</pre></div>
</div>
</dd>
<dt>parser.ml:</dt><dd><div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(*===---------------------------------------------------------------------===</span>
<span class="c"> * Parser</span>
<span class="c"> *===---------------------------------------------------------------------===*)</span>

<span class="c">(* binop_precedence - This holds the precedence for each binary operator that is</span>
<span class="c"> * defined *)</span>
<span class="k">let</span> <span class="n">binop_precedence</span><span class="o">:(</span><span class="kt">char</span><span class="o">,</span> <span class="kt">int</span><span class="o">)</span> <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">t</span> <span class="o">=</span> <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">create</span> <span class="mi">10</span>

<span class="c">(* precedence - Get the precedence of the pending binary operator token. *)</span>
<span class="k">let</span> <span class="n">precedence</span> <span class="n">c</span> <span class="o">=</span> <span class="k">try</span> <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">find</span> <span class="n">binop_precedence</span> <span class="n">c</span> <span class="k">with</span> <span class="nc">Not_found</span> <span class="o">-&gt;</span> <span class="o">-</span><span class="mi">1</span>

<span class="c">(* primary</span>
<span class="c"> *   ::= identifier</span>
<span class="c"> *   ::= numberexpr</span>
<span class="c"> *   ::= parenexpr</span>
<span class="c"> *   ::= ifexpr</span>
<span class="c"> *   ::= forexpr *)</span>
<span class="k">let</span> <span class="k">rec</span> <span class="n">parse_primary</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="c">(* numberexpr ::= number *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Number</span> <span class="n">n</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Number</span> <span class="n">n</span>

  <span class="c">(* parenexpr ::= &#39;(&#39; expression &#39;)&#39; *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;(&#39;</span><span class="o">;</span> <span class="n">e</span><span class="o">=</span><span class="n">parse_expr</span><span class="o">;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;)&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;)&#39;&quot;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">e</span>

  <span class="c">(* identifierexpr</span>
<span class="c">   *   ::= identifier</span>
<span class="c">   *   ::= identifier &#39;(&#39; argumentexpr &#39;)&#39; *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Ident</span> <span class="n">id</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="k">rec</span> <span class="n">parse_args</span> <span class="n">accumulator</span> <span class="o">=</span> <span class="n">parser</span>
        <span class="o">|</span> <span class="o">[&lt;</span> <span class="n">e</span><span class="o">=</span><span class="n">parse_expr</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
            <span class="k">begin</span> <span class="n">parser</span>
              <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;,&#39;</span><span class="o">;</span> <span class="n">e</span><span class="o">=</span><span class="n">parse_args</span> <span class="o">(</span><span class="n">e</span> <span class="o">::</span> <span class="n">accumulator</span><span class="o">)</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">e</span>
              <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">e</span> <span class="o">::</span> <span class="n">accumulator</span>
            <span class="k">end</span> <span class="n">stream</span>
        <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">accumulator</span>
      <span class="k">in</span>
      <span class="k">let</span> <span class="k">rec</span> <span class="n">parse_ident</span> <span class="n">id</span> <span class="o">=</span> <span class="n">parser</span>
        <span class="c">(* Call. *)</span>
        <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;(&#39;</span><span class="o">;</span>
             <span class="n">args</span><span class="o">=</span><span class="n">parse_args</span> <span class="bp">[]</span><span class="o">;</span>
             <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;)&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;)&#39;&quot;</span><span class="o">&gt;]</span> <span class="o">-&gt;</span>
            <span class="nn">Ast</span><span class="p">.</span><span class="nc">Call</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="nn">Array</span><span class="p">.</span><span class="n">of_list</span> <span class="o">(</span><span class="nn">List</span><span class="p">.</span><span class="n">rev</span> <span class="n">args</span><span class="o">))</span>

        <span class="c">(* Simple variable ref. *)</span>
        <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Variable</span> <span class="n">id</span>
      <span class="k">in</span>
      <span class="n">parse_ident</span> <span class="n">id</span> <span class="n">stream</span>

  <span class="c">(* ifexpr ::= &#39;if&#39; expr &#39;then&#39; expr &#39;else&#39; expr *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">If</span><span class="o">;</span> <span class="n">c</span><span class="o">=</span><span class="n">parse_expr</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Then</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;then&#39;&quot;</span><span class="o">;</span> <span class="n">t</span><span class="o">=</span><span class="n">parse_expr</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Else</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;else&#39;&quot;</span><span class="o">;</span> <span class="n">e</span><span class="o">=</span><span class="n">parse_expr</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="nn">Ast</span><span class="p">.</span><span class="nc">If</span> <span class="o">(</span><span class="n">c</span><span class="o">,</span> <span class="n">t</span><span class="o">,</span> <span class="n">e</span><span class="o">)</span>

  <span class="c">(* forexpr</span>
<span class="c">        ::= &#39;for&#39; identifier &#39;=&#39; expr &#39;,&#39; expr (&#39;,&#39; expr)? &#39;in&#39; expression *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">For</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Ident</span> <span class="n">id</span> <span class="o">??</span> <span class="s2">&quot;expected identifier after for&quot;</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;=&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;=&#39; after for&quot;</span><span class="o">;</span>
       <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">begin</span> <span class="n">parser</span>
        <span class="o">|</span> <span class="o">[&lt;</span>
             <span class="n">start</span><span class="o">=</span><span class="n">parse_expr</span><span class="o">;</span>
             <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;,&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;,&#39; after for&quot;</span><span class="o">;</span>
             <span class="n">end_</span><span class="o">=</span><span class="n">parse_expr</span><span class="o">;</span>
             <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
            <span class="k">let</span> <span class="n">step</span> <span class="o">=</span>
              <span class="k">begin</span> <span class="n">parser</span>
              <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;,&#39;</span><span class="o">;</span> <span class="n">step</span><span class="o">=</span><span class="n">parse_expr</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="nc">Some</span> <span class="n">step</span>
              <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="nc">None</span>
              <span class="k">end</span> <span class="n">stream</span>
            <span class="k">in</span>
            <span class="k">begin</span> <span class="n">parser</span>
            <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">In</span><span class="o">;</span> <span class="n">body</span><span class="o">=</span><span class="n">parse_expr</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
                <span class="nn">Ast</span><span class="p">.</span><span class="nc">For</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="n">start</span><span class="o">,</span> <span class="n">end_</span><span class="o">,</span> <span class="n">step</span><span class="o">,</span> <span class="n">body</span><span class="o">)</span>
            <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
                <span class="k">raise</span> <span class="o">(</span><span class="nn">Stream</span><span class="p">.</span><span class="nc">Error</span> <span class="s2">&quot;expected &#39;in&#39; after for&quot;</span><span class="o">)</span>
            <span class="k">end</span> <span class="n">stream</span>
        <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
            <span class="k">raise</span> <span class="o">(</span><span class="nn">Stream</span><span class="p">.</span><span class="nc">Error</span> <span class="s2">&quot;expected &#39;=&#39; after for&quot;</span><span class="o">)</span>
      <span class="k">end</span> <span class="n">stream</span>

  <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="k">raise</span> <span class="o">(</span><span class="nn">Stream</span><span class="p">.</span><span class="nc">Error</span> <span class="s2">&quot;unknown token when expecting an expression.&quot;</span><span class="o">)</span>

<span class="c">(* unary</span>
<span class="c"> *   ::= primary</span>
<span class="c"> *   ::= &#39;!&#39; unary *)</span>
<span class="ow">and</span> <span class="n">parse_unary</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="c">(* If this is a unary operator, read it. *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="n">op</span> <span class="k">when</span> <span class="n">op</span> <span class="o">!=</span> <span class="sc">&#39;(&#39;</span> <span class="o">&amp;&amp;</span> <span class="n">op</span> <span class="o">!=</span> <span class="sc">&#39;)&#39;</span><span class="o">;</span> <span class="n">operand</span><span class="o">=</span><span class="n">parse_expr</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="nn">Ast</span><span class="p">.</span><span class="nc">Unary</span> <span class="o">(</span><span class="n">op</span><span class="o">,</span> <span class="n">operand</span><span class="o">)</span>

  <span class="c">(* If the current token is not an operator, it must be a primary expr. *)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">parse_primary</span> <span class="n">stream</span>

<span class="c">(* binoprhs</span>
<span class="c"> *   ::= (&#39;+&#39; primary)* *)</span>
<span class="ow">and</span> <span class="n">parse_bin_rhs</span> <span class="n">expr_prec</span> <span class="n">lhs</span> <span class="n">stream</span> <span class="o">=</span>
  <span class="k">match</span> <span class="nn">Stream</span><span class="p">.</span><span class="n">peek</span> <span class="n">stream</span> <span class="k">with</span>
  <span class="c">(* If this is a binop, find its precedence. *)</span>
  <span class="o">|</span> <span class="nc">Some</span> <span class="o">(</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="n">c</span><span class="o">)</span> <span class="k">when</span> <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">mem</span> <span class="n">binop_precedence</span> <span class="n">c</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">token_prec</span> <span class="o">=</span> <span class="n">precedence</span> <span class="n">c</span> <span class="k">in</span>

      <span class="c">(* If this is a binop that binds at least as tightly as the current binop,</span>
<span class="c">       * consume it, otherwise we are done. *)</span>
      <span class="k">if</span> <span class="n">token_prec</span> <span class="o">&lt;</span> <span class="n">expr_prec</span> <span class="k">then</span> <span class="n">lhs</span> <span class="k">else</span> <span class="k">begin</span>
        <span class="c">(* Eat the binop. *)</span>
        <span class="nn">Stream</span><span class="p">.</span><span class="n">junk</span> <span class="n">stream</span><span class="o">;</span>

        <span class="c">(* Parse the unary expression after the binary operator. *)</span>
        <span class="k">let</span> <span class="n">rhs</span> <span class="o">=</span> <span class="n">parse_unary</span> <span class="n">stream</span> <span class="k">in</span>

        <span class="c">(* Okay, we know this is a binop. *)</span>
        <span class="k">let</span> <span class="n">rhs</span> <span class="o">=</span>
          <span class="k">match</span> <span class="nn">Stream</span><span class="p">.</span><span class="n">peek</span> <span class="n">stream</span> <span class="k">with</span>
          <span class="o">|</span> <span class="nc">Some</span> <span class="o">(</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="n">c2</span><span class="o">)</span> <span class="o">-&gt;</span>
              <span class="c">(* If BinOp binds less tightly with rhs than the operator after</span>
<span class="c">               * rhs, let the pending operator take rhs as its lhs. *)</span>
              <span class="k">let</span> <span class="n">next_prec</span> <span class="o">=</span> <span class="n">precedence</span> <span class="n">c2</span> <span class="k">in</span>
              <span class="k">if</span> <span class="n">token_prec</span> <span class="o">&lt;</span> <span class="n">next_prec</span>
              <span class="k">then</span> <span class="n">parse_bin_rhs</span> <span class="o">(</span><span class="n">token_prec</span> <span class="o">+</span> <span class="mi">1</span><span class="o">)</span> <span class="n">rhs</span> <span class="n">stream</span>
              <span class="k">else</span> <span class="n">rhs</span>
          <span class="o">|</span> <span class="o">_</span> <span class="o">-&gt;</span> <span class="n">rhs</span>
        <span class="k">in</span>

        <span class="c">(* Merge lhs/rhs. *)</span>
        <span class="k">let</span> <span class="n">lhs</span> <span class="o">=</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Binary</span> <span class="o">(</span><span class="n">c</span><span class="o">,</span> <span class="n">lhs</span><span class="o">,</span> <span class="n">rhs</span><span class="o">)</span> <span class="k">in</span>
        <span class="n">parse_bin_rhs</span> <span class="n">expr_prec</span> <span class="n">lhs</span> <span class="n">stream</span>
      <span class="k">end</span>
  <span class="o">|</span> <span class="o">_</span> <span class="o">-&gt;</span> <span class="n">lhs</span>

<span class="c">(* expression</span>
<span class="c"> *   ::= primary binoprhs *)</span>
<span class="ow">and</span> <span class="n">parse_expr</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="n">lhs</span><span class="o">=</span><span class="n">parse_unary</span><span class="o">;</span> <span class="n">stream</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">parse_bin_rhs</span> <span class="mi">0</span> <span class="n">lhs</span> <span class="n">stream</span>

<span class="c">(* prototype</span>
<span class="c"> *   ::= id &#39;(&#39; id* &#39;)&#39;</span>
<span class="c"> *   ::= binary LETTER number? (id, id)</span>
<span class="c"> *   ::= unary LETTER number? (id) *)</span>
<span class="k">let</span> <span class="n">parse_prototype</span> <span class="o">=</span>
  <span class="k">let</span> <span class="k">rec</span> <span class="n">parse_args</span> <span class="n">accumulator</span> <span class="o">=</span> <span class="n">parser</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Ident</span> <span class="n">id</span><span class="o">;</span> <span class="n">e</span><span class="o">=</span><span class="n">parse_args</span> <span class="o">(</span><span class="n">id</span><span class="o">::</span><span class="n">accumulator</span><span class="o">)</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">e</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">accumulator</span>
  <span class="k">in</span>
  <span class="k">let</span> <span class="n">parse_operator</span> <span class="o">=</span> <span class="n">parser</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Unary</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="s2">&quot;unary&quot;</span><span class="o">,</span> <span class="mi">1</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Binary</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="s2">&quot;binary&quot;</span><span class="o">,</span> <span class="mi">2</span>
  <span class="k">in</span>
  <span class="k">let</span> <span class="n">parse_binary_precedence</span> <span class="o">=</span> <span class="n">parser</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Number</span> <span class="n">n</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">int_of_float</span> <span class="n">n</span>
    <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="mi">30</span>
  <span class="k">in</span>
  <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Ident</span> <span class="n">id</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;(&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;(&#39; in prototype&quot;</span><span class="o">;</span>
       <span class="n">args</span><span class="o">=</span><span class="n">parse_args</span> <span class="bp">[]</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;)&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;)&#39; in prototype&quot;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="c">(* success. *)</span>
      <span class="nn">Ast</span><span class="p">.</span><span class="nc">Prototype</span> <span class="o">(</span><span class="n">id</span><span class="o">,</span> <span class="nn">Array</span><span class="p">.</span><span class="n">of_list</span> <span class="o">(</span><span class="nn">List</span><span class="p">.</span><span class="n">rev</span> <span class="n">args</span><span class="o">))</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">(</span><span class="n">prefix</span><span class="o">,</span> <span class="n">kind</span><span class="o">)=</span><span class="n">parse_operator</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="n">op</span> <span class="o">??</span> <span class="s2">&quot;expected an operator&quot;</span><span class="o">;</span>
       <span class="c">(* Read the precedence if present. *)</span>
       <span class="n">binary_precedence</span><span class="o">=</span><span class="n">parse_binary_precedence</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;(&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;(&#39; in prototype&quot;</span><span class="o">;</span>
        <span class="n">args</span><span class="o">=</span><span class="n">parse_args</span> <span class="bp">[]</span><span class="o">;</span>
       <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;)&#39;</span> <span class="o">??</span> <span class="s2">&quot;expected &#39;)&#39; in prototype&quot;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">name</span> <span class="o">=</span> <span class="n">prefix</span> <span class="o">^</span> <span class="o">(</span><span class="nn">String</span><span class="p">.</span><span class="n">make</span> <span class="mi">1</span> <span class="n">op</span><span class="o">)</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">args</span> <span class="o">=</span> <span class="nn">Array</span><span class="p">.</span><span class="n">of_list</span> <span class="o">(</span><span class="nn">List</span><span class="p">.</span><span class="n">rev</span> <span class="n">args</span><span class="o">)</span> <span class="k">in</span>

      <span class="c">(* Verify right number of arguments for operator. *)</span>
      <span class="k">if</span> <span class="nn">Array</span><span class="p">.</span><span class="n">length</span> <span class="n">args</span> <span class="o">!=</span> <span class="n">kind</span>
      <span class="k">then</span> <span class="k">raise</span> <span class="o">(</span><span class="nn">Stream</span><span class="p">.</span><span class="nc">Error</span> <span class="s2">&quot;invalid number of operands for operator&quot;</span><span class="o">)</span>
      <span class="k">else</span>
        <span class="k">if</span> <span class="n">kind</span> <span class="o">==</span> <span class="mi">1</span> <span class="k">then</span>
          <span class="nn">Ast</span><span class="p">.</span><span class="nc">Prototype</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">args</span><span class="o">)</span>
        <span class="k">else</span>
          <span class="nn">Ast</span><span class="p">.</span><span class="nc">BinOpPrototype</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">args</span><span class="o">,</span> <span class="n">binary_precedence</span><span class="o">)</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="k">raise</span> <span class="o">(</span><span class="nn">Stream</span><span class="p">.</span><span class="nc">Error</span> <span class="s2">&quot;expected function name in prototype&quot;</span><span class="o">)</span>

<span class="c">(* definition ::= &#39;def&#39; prototype expression *)</span>
<span class="k">let</span> <span class="n">parse_definition</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Def</span><span class="o">;</span> <span class="n">p</span><span class="o">=</span><span class="n">parse_prototype</span><span class="o">;</span> <span class="n">e</span><span class="o">=</span><span class="n">parse_expr</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="nn">Ast</span><span class="p">.</span><span class="nc">Function</span> <span class="o">(</span><span class="n">p</span><span class="o">,</span> <span class="n">e</span><span class="o">)</span>

<span class="c">(* toplevelexpr ::= expression *)</span>
<span class="k">let</span> <span class="n">parse_toplevel</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="n">e</span><span class="o">=</span><span class="n">parse_expr</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span>
      <span class="c">(* Make an anonymous proto. *)</span>
      <span class="nn">Ast</span><span class="p">.</span><span class="nc">Function</span> <span class="o">(</span><span class="nn">Ast</span><span class="p">.</span><span class="nc">Prototype</span> <span class="o">(</span><span class="s2">&quot;&quot;</span><span class="o">,</span> <span class="o">[||]),</span> <span class="n">e</span><span class="o">)</span>

<span class="c">(*  external ::= &#39;extern&#39; prototype *)</span>
<span class="k">let</span> <span class="n">parse_extern</span> <span class="o">=</span> <span class="n">parser</span>
  <span class="o">|</span> <span class="o">[&lt;</span> <span class="k">&#39;</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Extern</span><span class="o">;</span> <span class="n">e</span><span class="o">=</span><span class="n">parse_prototype</span> <span class="o">&gt;]</span> <span class="o">-&gt;</span> <span class="n">e</span>
</pre></div>
</div>
</dd>
<dt>codegen.ml:</dt><dd><div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(*===----------------------------------------------------------------------===</span>
<span class="c"> * Code Generation</span>
<span class="c"> *===----------------------------------------------------------------------===*)</span>

<span class="k">open</span> <span class="nc">Llvm</span>

<span class="k">exception</span> <span class="nc">Error</span> <span class="k">of</span> <span class="kt">string</span>

<span class="k">let</span> <span class="n">context</span> <span class="o">=</span> <span class="n">global_context</span> <span class="bp">()</span>
<span class="k">let</span> <span class="n">the_module</span> <span class="o">=</span> <span class="n">create_module</span> <span class="n">context</span> <span class="s2">&quot;my cool jit&quot;</span>
<span class="k">let</span> <span class="n">builder</span> <span class="o">=</span> <span class="n">builder</span> <span class="n">context</span>
<span class="k">let</span> <span class="n">named_values</span><span class="o">:(</span><span class="kt">string</span><span class="o">,</span> <span class="n">llvalue</span><span class="o">)</span> <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">t</span> <span class="o">=</span> <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">create</span> <span class="mi">10</span>
<span class="k">let</span> <span class="n">double_type</span> <span class="o">=</span> <span class="n">double_type</span> <span class="n">context</span>

<span class="k">let</span> <span class="k">rec</span> <span class="n">codegen_expr</span> <span class="o">=</span> <span class="k">function</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Number</span> <span class="n">n</span> <span class="o">-&gt;</span> <span class="n">const_float</span> <span class="n">double_type</span> <span class="n">n</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Variable</span> <span class="n">name</span> <span class="o">-&gt;</span>
      <span class="o">(</span><span class="k">try</span> <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">find</span> <span class="n">named_values</span> <span class="n">name</span> <span class="k">with</span>
        <span class="o">|</span> <span class="nc">Not_found</span> <span class="o">-&gt;</span> <span class="k">raise</span> <span class="o">(</span><span class="nc">Error</span> <span class="s2">&quot;unknown variable name&quot;</span><span class="o">))</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Unary</span> <span class="o">(</span><span class="n">op</span><span class="o">,</span> <span class="n">operand</span><span class="o">)</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">operand</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">operand</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">callee</span> <span class="o">=</span> <span class="s2">&quot;unary&quot;</span> <span class="o">^</span> <span class="o">(</span><span class="nn">String</span><span class="p">.</span><span class="n">make</span> <span class="mi">1</span> <span class="n">op</span><span class="o">)</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">callee</span> <span class="o">=</span>
        <span class="k">match</span> <span class="n">lookup_function</span> <span class="n">callee</span> <span class="n">the_module</span> <span class="k">with</span>
        <span class="o">|</span> <span class="nc">Some</span> <span class="n">callee</span> <span class="o">-&gt;</span> <span class="n">callee</span>
        <span class="o">|</span> <span class="nc">None</span> <span class="o">-&gt;</span> <span class="k">raise</span> <span class="o">(</span><span class="nc">Error</span> <span class="s2">&quot;unknown unary operator&quot;</span><span class="o">)</span>
      <span class="k">in</span>
      <span class="n">build_call</span> <span class="n">callee</span> <span class="o">[|</span><span class="n">operand</span><span class="o">|]</span> <span class="s2">&quot;unop&quot;</span> <span class="n">builder</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Binary</span> <span class="o">(</span><span class="n">op</span><span class="o">,</span> <span class="n">lhs</span><span class="o">,</span> <span class="n">rhs</span><span class="o">)</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">lhs_val</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">lhs</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">rhs_val</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">rhs</span> <span class="k">in</span>
      <span class="k">begin</span>
        <span class="k">match</span> <span class="n">op</span> <span class="k">with</span>
        <span class="o">|</span> <span class="sc">&#39;+&#39;</span> <span class="o">-&gt;</span> <span class="n">build_add</span> <span class="n">lhs_val</span> <span class="n">rhs_val</span> <span class="s2">&quot;addtmp&quot;</span> <span class="n">builder</span>
        <span class="o">|</span> <span class="sc">&#39;-&#39;</span> <span class="o">-&gt;</span> <span class="n">build_sub</span> <span class="n">lhs_val</span> <span class="n">rhs_val</span> <span class="s2">&quot;subtmp&quot;</span> <span class="n">builder</span>
        <span class="o">|</span> <span class="sc">&#39;*&#39;</span> <span class="o">-&gt;</span> <span class="n">build_mul</span> <span class="n">lhs_val</span> <span class="n">rhs_val</span> <span class="s2">&quot;multmp&quot;</span> <span class="n">builder</span>
        <span class="o">|</span> <span class="sc">&#39;&lt;&#39;</span> <span class="o">-&gt;</span>
            <span class="c">(* Convert bool 0/1 to double 0.0 or 1.0 *)</span>
            <span class="k">let</span> <span class="n">i</span> <span class="o">=</span> <span class="n">build_fcmp</span> <span class="nn">Fcmp</span><span class="p">.</span><span class="nc">Ult</span> <span class="n">lhs_val</span> <span class="n">rhs_val</span> <span class="s2">&quot;cmptmp&quot;</span> <span class="n">builder</span> <span class="k">in</span>
            <span class="n">build_uitofp</span> <span class="n">i</span> <span class="n">double_type</span> <span class="s2">&quot;booltmp&quot;</span> <span class="n">builder</span>
        <span class="o">|</span> <span class="o">_</span> <span class="o">-&gt;</span>
            <span class="c">(* If it wasn&#39;t a builtin binary operator, it must be a user defined</span>
<span class="c">             * one. Emit a call to it. *)</span>
            <span class="k">let</span> <span class="n">callee</span> <span class="o">=</span> <span class="s2">&quot;binary&quot;</span> <span class="o">^</span> <span class="o">(</span><span class="nn">String</span><span class="p">.</span><span class="n">make</span> <span class="mi">1</span> <span class="n">op</span><span class="o">)</span> <span class="k">in</span>
            <span class="k">let</span> <span class="n">callee</span> <span class="o">=</span>
              <span class="k">match</span> <span class="n">lookup_function</span> <span class="n">callee</span> <span class="n">the_module</span> <span class="k">with</span>
              <span class="o">|</span> <span class="nc">Some</span> <span class="n">callee</span> <span class="o">-&gt;</span> <span class="n">callee</span>
              <span class="o">|</span> <span class="nc">None</span> <span class="o">-&gt;</span> <span class="k">raise</span> <span class="o">(</span><span class="nc">Error</span> <span class="s2">&quot;binary operator not found!&quot;</span><span class="o">)</span>
            <span class="k">in</span>
            <span class="n">build_call</span> <span class="n">callee</span> <span class="o">[|</span><span class="n">lhs_val</span><span class="o">;</span> <span class="n">rhs_val</span><span class="o">|]</span> <span class="s2">&quot;binop&quot;</span> <span class="n">builder</span>
      <span class="k">end</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Call</span> <span class="o">(</span><span class="n">callee</span><span class="o">,</span> <span class="n">args</span><span class="o">)</span> <span class="o">-&gt;</span>
      <span class="c">(* Look up the name in the module table. *)</span>
      <span class="k">let</span> <span class="n">callee</span> <span class="o">=</span>
        <span class="k">match</span> <span class="n">lookup_function</span> <span class="n">callee</span> <span class="n">the_module</span> <span class="k">with</span>
        <span class="o">|</span> <span class="nc">Some</span> <span class="n">callee</span> <span class="o">-&gt;</span> <span class="n">callee</span>
        <span class="o">|</span> <span class="nc">None</span> <span class="o">-&gt;</span> <span class="k">raise</span> <span class="o">(</span><span class="nc">Error</span> <span class="s2">&quot;unknown function referenced&quot;</span><span class="o">)</span>
      <span class="k">in</span>
      <span class="k">let</span> <span class="n">params</span> <span class="o">=</span> <span class="n">params</span> <span class="n">callee</span> <span class="k">in</span>

      <span class="c">(* If argument mismatch error. *)</span>
      <span class="k">if</span> <span class="nn">Array</span><span class="p">.</span><span class="n">length</span> <span class="n">params</span> <span class="o">==</span> <span class="nn">Array</span><span class="p">.</span><span class="n">length</span> <span class="n">args</span> <span class="k">then</span> <span class="bp">()</span> <span class="k">else</span>
        <span class="k">raise</span> <span class="o">(</span><span class="nc">Error</span> <span class="s2">&quot;incorrect # arguments passed&quot;</span><span class="o">);</span>
      <span class="k">let</span> <span class="n">args</span> <span class="o">=</span> <span class="nn">Array</span><span class="p">.</span><span class="n">map</span> <span class="n">codegen_expr</span> <span class="n">args</span> <span class="k">in</span>
      <span class="n">build_call</span> <span class="n">callee</span> <span class="n">args</span> <span class="s2">&quot;calltmp&quot;</span> <span class="n">builder</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">If</span> <span class="o">(</span><span class="n">cond</span><span class="o">,</span> <span class="n">then_</span><span class="o">,</span> <span class="n">else_</span><span class="o">)</span> <span class="o">-&gt;</span>
      <span class="k">let</span> <span class="n">cond</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">cond</span> <span class="k">in</span>

      <span class="c">(* Convert condition to a bool by comparing equal to 0.0 *)</span>
      <span class="k">let</span> <span class="n">zero</span> <span class="o">=</span> <span class="n">const_float</span> <span class="n">double_type</span> <span class="mi">0</span><span class="o">.</span><span class="mi">0</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">cond_val</span> <span class="o">=</span> <span class="n">build_fcmp</span> <span class="nn">Fcmp</span><span class="p">.</span><span class="nc">One</span> <span class="n">cond</span> <span class="n">zero</span> <span class="s2">&quot;ifcond&quot;</span> <span class="n">builder</span> <span class="k">in</span>

      <span class="c">(* Grab the first block so that we might later add the conditional branch</span>
<span class="c">       * to it at the end of the function. *)</span>
      <span class="k">let</span> <span class="n">start_bb</span> <span class="o">=</span> <span class="n">insertion_block</span> <span class="n">builder</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">the_function</span> <span class="o">=</span> <span class="n">block_parent</span> <span class="n">start_bb</span> <span class="k">in</span>

      <span class="k">let</span> <span class="n">then_bb</span> <span class="o">=</span> <span class="n">append_block</span> <span class="n">context</span> <span class="s2">&quot;then&quot;</span> <span class="n">the_function</span> <span class="k">in</span>

      <span class="c">(* Emit &#39;then&#39; value. *)</span>
      <span class="n">position_at_end</span> <span class="n">then_bb</span> <span class="n">builder</span><span class="o">;</span>
      <span class="k">let</span> <span class="n">then_val</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">then_</span> <span class="k">in</span>

      <span class="c">(* Codegen of &#39;then&#39; can change the current block, update then_bb for the</span>
<span class="c">       * phi. We create a new name because one is used for the phi node, and the</span>
<span class="c">       * other is used for the conditional branch. *)</span>
      <span class="k">let</span> <span class="n">new_then_bb</span> <span class="o">=</span> <span class="n">insertion_block</span> <span class="n">builder</span> <span class="k">in</span>

      <span class="c">(* Emit &#39;else&#39; value. *)</span>
      <span class="k">let</span> <span class="n">else_bb</span> <span class="o">=</span> <span class="n">append_block</span> <span class="n">context</span> <span class="s2">&quot;else&quot;</span> <span class="n">the_function</span> <span class="k">in</span>
      <span class="n">position_at_end</span> <span class="n">else_bb</span> <span class="n">builder</span><span class="o">;</span>
      <span class="k">let</span> <span class="n">else_val</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">else_</span> <span class="k">in</span>

      <span class="c">(* Codegen of &#39;else&#39; can change the current block, update else_bb for the</span>
<span class="c">       * phi. *)</span>
      <span class="k">let</span> <span class="n">new_else_bb</span> <span class="o">=</span> <span class="n">insertion_block</span> <span class="n">builder</span> <span class="k">in</span>

      <span class="c">(* Emit merge block. *)</span>
      <span class="k">let</span> <span class="n">merge_bb</span> <span class="o">=</span> <span class="n">append_block</span> <span class="n">context</span> <span class="s2">&quot;ifcont&quot;</span> <span class="n">the_function</span> <span class="k">in</span>
      <span class="n">position_at_end</span> <span class="n">merge_bb</span> <span class="n">builder</span><span class="o">;</span>
      <span class="k">let</span> <span class="n">incoming</span> <span class="o">=</span> <span class="o">[(</span><span class="n">then_val</span><span class="o">,</span> <span class="n">new_then_bb</span><span class="o">);</span> <span class="o">(</span><span class="n">else_val</span><span class="o">,</span> <span class="n">new_else_bb</span><span class="o">)]</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">phi</span> <span class="o">=</span> <span class="n">build_phi</span> <span class="n">incoming</span> <span class="s2">&quot;iftmp&quot;</span> <span class="n">builder</span> <span class="k">in</span>

      <span class="c">(* Return to the start block to add the conditional branch. *)</span>
      <span class="n">position_at_end</span> <span class="n">start_bb</span> <span class="n">builder</span><span class="o">;</span>
      <span class="n">ignore</span> <span class="o">(</span><span class="n">build_cond_br</span> <span class="n">cond_val</span> <span class="n">then_bb</span> <span class="n">else_bb</span> <span class="n">builder</span><span class="o">);</span>

      <span class="c">(* Set a unconditional branch at the end of the &#39;then&#39; block and the</span>
<span class="c">       * &#39;else&#39; block to the &#39;merge&#39; block. *)</span>
      <span class="n">position_at_end</span> <span class="n">new_then_bb</span> <span class="n">builder</span><span class="o">;</span> <span class="n">ignore</span> <span class="o">(</span><span class="n">build_br</span> <span class="n">merge_bb</span> <span class="n">builder</span><span class="o">);</span>
      <span class="n">position_at_end</span> <span class="n">new_else_bb</span> <span class="n">builder</span><span class="o">;</span> <span class="n">ignore</span> <span class="o">(</span><span class="n">build_br</span> <span class="n">merge_bb</span> <span class="n">builder</span><span class="o">);</span>

      <span class="c">(* Finally, set the builder to the end of the merge block. *)</span>
      <span class="n">position_at_end</span> <span class="n">merge_bb</span> <span class="n">builder</span><span class="o">;</span>

      <span class="n">phi</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">For</span> <span class="o">(</span><span class="n">var_name</span><span class="o">,</span> <span class="n">start</span><span class="o">,</span> <span class="n">end_</span><span class="o">,</span> <span class="n">step</span><span class="o">,</span> <span class="n">body</span><span class="o">)</span> <span class="o">-&gt;</span>
      <span class="c">(* Emit the start code first, without &#39;variable&#39; in scope. *)</span>
      <span class="k">let</span> <span class="n">start_val</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">start</span> <span class="k">in</span>

      <span class="c">(* Make the new basic block for the loop header, inserting after current</span>
<span class="c">       * block. *)</span>
      <span class="k">let</span> <span class="n">preheader_bb</span> <span class="o">=</span> <span class="n">insertion_block</span> <span class="n">builder</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">the_function</span> <span class="o">=</span> <span class="n">block_parent</span> <span class="n">preheader_bb</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">loop_bb</span> <span class="o">=</span> <span class="n">append_block</span> <span class="n">context</span> <span class="s2">&quot;loop&quot;</span> <span class="n">the_function</span> <span class="k">in</span>

      <span class="c">(* Insert an explicit fall through from the current block to the</span>
<span class="c">       * loop_bb. *)</span>
      <span class="n">ignore</span> <span class="o">(</span><span class="n">build_br</span> <span class="n">loop_bb</span> <span class="n">builder</span><span class="o">);</span>

      <span class="c">(* Start insertion in loop_bb. *)</span>
      <span class="n">position_at_end</span> <span class="n">loop_bb</span> <span class="n">builder</span><span class="o">;</span>

      <span class="c">(* Start the PHI node with an entry for start. *)</span>
      <span class="k">let</span> <span class="n">variable</span> <span class="o">=</span> <span class="n">build_phi</span> <span class="o">[(</span><span class="n">start_val</span><span class="o">,</span> <span class="n">preheader_bb</span><span class="o">)]</span> <span class="n">var_name</span> <span class="n">builder</span> <span class="k">in</span>

      <span class="c">(* Within the loop, the variable is defined equal to the PHI node. If it</span>
<span class="c">       * shadows an existing variable, we have to restore it, so save it</span>
<span class="c">       * now. *)</span>
      <span class="k">let</span> <span class="n">old_val</span> <span class="o">=</span>
        <span class="k">try</span> <span class="nc">Some</span> <span class="o">(</span><span class="nn">Hashtbl</span><span class="p">.</span><span class="n">find</span> <span class="n">named_values</span> <span class="n">var_name</span><span class="o">)</span> <span class="k">with</span> <span class="nc">Not_found</span> <span class="o">-&gt;</span> <span class="nc">None</span>
      <span class="k">in</span>
      <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">add</span> <span class="n">named_values</span> <span class="n">var_name</span> <span class="n">variable</span><span class="o">;</span>

      <span class="c">(* Emit the body of the loop.  This, like any other expr, can change the</span>
<span class="c">       * current BB.  Note that we ignore the value computed by the body, but</span>
<span class="c">       * don&#39;t allow an error *)</span>
      <span class="n">ignore</span> <span class="o">(</span><span class="n">codegen_expr</span> <span class="n">body</span><span class="o">);</span>

      <span class="c">(* Emit the step value. *)</span>
      <span class="k">let</span> <span class="n">step_val</span> <span class="o">=</span>
        <span class="k">match</span> <span class="n">step</span> <span class="k">with</span>
        <span class="o">|</span> <span class="nc">Some</span> <span class="n">step</span> <span class="o">-&gt;</span> <span class="n">codegen_expr</span> <span class="n">step</span>
        <span class="c">(* If not specified, use 1.0. *)</span>
        <span class="o">|</span> <span class="nc">None</span> <span class="o">-&gt;</span> <span class="n">const_float</span> <span class="n">double_type</span> <span class="mi">1</span><span class="o">.</span><span class="mi">0</span>
      <span class="k">in</span>

      <span class="k">let</span> <span class="n">next_var</span> <span class="o">=</span> <span class="n">build_add</span> <span class="n">variable</span> <span class="n">step_val</span> <span class="s2">&quot;nextvar&quot;</span> <span class="n">builder</span> <span class="k">in</span>

      <span class="c">(* Compute the end condition. *)</span>
      <span class="k">let</span> <span class="n">end_cond</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">end_</span> <span class="k">in</span>

      <span class="c">(* Convert condition to a bool by comparing equal to 0.0. *)</span>
      <span class="k">let</span> <span class="n">zero</span> <span class="o">=</span> <span class="n">const_float</span> <span class="n">double_type</span> <span class="mi">0</span><span class="o">.</span><span class="mi">0</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">end_cond</span> <span class="o">=</span> <span class="n">build_fcmp</span> <span class="nn">Fcmp</span><span class="p">.</span><span class="nc">One</span> <span class="n">end_cond</span> <span class="n">zero</span> <span class="s2">&quot;loopcond&quot;</span> <span class="n">builder</span> <span class="k">in</span>

      <span class="c">(* Create the &quot;after loop&quot; block and insert it. *)</span>
      <span class="k">let</span> <span class="n">loop_end_bb</span> <span class="o">=</span> <span class="n">insertion_block</span> <span class="n">builder</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">after_bb</span> <span class="o">=</span> <span class="n">append_block</span> <span class="n">context</span> <span class="s2">&quot;afterloop&quot;</span> <span class="n">the_function</span> <span class="k">in</span>

      <span class="c">(* Insert the conditional branch into the end of loop_end_bb. *)</span>
      <span class="n">ignore</span> <span class="o">(</span><span class="n">build_cond_br</span> <span class="n">end_cond</span> <span class="n">loop_bb</span> <span class="n">after_bb</span> <span class="n">builder</span><span class="o">);</span>

      <span class="c">(* Any new code will be inserted in after_bb. *)</span>
      <span class="n">position_at_end</span> <span class="n">after_bb</span> <span class="n">builder</span><span class="o">;</span>

      <span class="c">(* Add a new entry to the PHI node for the backedge. *)</span>
      <span class="n">add_incoming</span> <span class="o">(</span><span class="n">next_var</span><span class="o">,</span> <span class="n">loop_end_bb</span><span class="o">)</span> <span class="n">variable</span><span class="o">;</span>

      <span class="c">(* Restore the unshadowed variable. *)</span>
      <span class="k">begin</span> <span class="k">match</span> <span class="n">old_val</span> <span class="k">with</span>
      <span class="o">|</span> <span class="nc">Some</span> <span class="n">old_val</span> <span class="o">-&gt;</span> <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">add</span> <span class="n">named_values</span> <span class="n">var_name</span> <span class="n">old_val</span>
      <span class="o">|</span> <span class="nc">None</span> <span class="o">-&gt;</span> <span class="bp">()</span>
      <span class="k">end</span><span class="o">;</span>

      <span class="c">(* for expr always returns 0.0. *)</span>
      <span class="n">const_null</span> <span class="n">double_type</span>

<span class="k">let</span> <span class="n">codegen_proto</span> <span class="o">=</span> <span class="k">function</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Prototype</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">args</span><span class="o">)</span> <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">BinOpPrototype</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">args</span><span class="o">,</span> <span class="o">_)</span> <span class="o">-&gt;</span>
      <span class="c">(* Make the function type: double(double,double) etc. *)</span>
      <span class="k">let</span> <span class="n">doubles</span> <span class="o">=</span> <span class="nn">Array</span><span class="p">.</span><span class="n">make</span> <span class="o">(</span><span class="nn">Array</span><span class="p">.</span><span class="n">length</span> <span class="n">args</span><span class="o">)</span> <span class="n">double_type</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">ft</span> <span class="o">=</span> <span class="n">function_type</span> <span class="n">double_type</span> <span class="n">doubles</span> <span class="k">in</span>
      <span class="k">let</span> <span class="n">f</span> <span class="o">=</span>
        <span class="k">match</span> <span class="n">lookup_function</span> <span class="n">name</span> <span class="n">the_module</span> <span class="k">with</span>
        <span class="o">|</span> <span class="nc">None</span> <span class="o">-&gt;</span> <span class="n">declare_function</span> <span class="n">name</span> <span class="n">ft</span> <span class="n">the_module</span>

        <span class="c">(* If &#39;f&#39; conflicted, there was already something named &#39;name&#39;. If it</span>
<span class="c">         * has a body, don&#39;t allow redefinition or reextern. *)</span>
        <span class="o">|</span> <span class="nc">Some</span> <span class="n">f</span> <span class="o">-&gt;</span>
            <span class="c">(* If &#39;f&#39; already has a body, reject this. *)</span>
            <span class="k">if</span> <span class="n">block_begin</span> <span class="n">f</span> <span class="o">&lt;&gt;</span> <span class="nc">At_end</span> <span class="n">f</span> <span class="k">then</span>
              <span class="k">raise</span> <span class="o">(</span><span class="nc">Error</span> <span class="s2">&quot;redefinition of function&quot;</span><span class="o">);</span>

            <span class="c">(* If &#39;f&#39; took a different number of arguments, reject. *)</span>
            <span class="k">if</span> <span class="n">element_type</span> <span class="o">(</span><span class="n">type_of</span> <span class="n">f</span><span class="o">)</span> <span class="o">&lt;&gt;</span> <span class="n">ft</span> <span class="k">then</span>
              <span class="k">raise</span> <span class="o">(</span><span class="nc">Error</span> <span class="s2">&quot;redefinition of function with different # args&quot;</span><span class="o">);</span>
            <span class="n">f</span>
      <span class="k">in</span>

      <span class="c">(* Set names for all arguments. *)</span>
      <span class="nn">Array</span><span class="p">.</span><span class="n">iteri</span> <span class="o">(</span><span class="k">fun</span> <span class="n">i</span> <span class="n">a</span> <span class="o">-&gt;</span>
        <span class="k">let</span> <span class="n">n</span> <span class="o">=</span> <span class="n">args</span><span class="o">.(</span><span class="n">i</span><span class="o">)</span> <span class="k">in</span>
        <span class="n">set_value_name</span> <span class="n">n</span> <span class="n">a</span><span class="o">;</span>
        <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">add</span> <span class="n">named_values</span> <span class="n">n</span> <span class="n">a</span><span class="o">;</span>
      <span class="o">)</span> <span class="o">(</span><span class="n">params</span> <span class="n">f</span><span class="o">);</span>
      <span class="n">f</span>

<span class="k">let</span> <span class="n">codegen_func</span> <span class="n">the_fpm</span> <span class="o">=</span> <span class="k">function</span>
  <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Function</span> <span class="o">(</span><span class="n">proto</span><span class="o">,</span> <span class="n">body</span><span class="o">)</span> <span class="o">-&gt;</span>
      <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">clear</span> <span class="n">named_values</span><span class="o">;</span>
      <span class="k">let</span> <span class="n">the_function</span> <span class="o">=</span> <span class="n">codegen_proto</span> <span class="n">proto</span> <span class="k">in</span>

      <span class="c">(* If this is an operator, install it. *)</span>
      <span class="k">begin</span> <span class="k">match</span> <span class="n">proto</span> <span class="k">with</span>
      <span class="o">|</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">BinOpPrototype</span> <span class="o">(</span><span class="n">name</span><span class="o">,</span> <span class="n">args</span><span class="o">,</span> <span class="n">prec</span><span class="o">)</span> <span class="o">-&gt;</span>
          <span class="k">let</span> <span class="n">op</span> <span class="o">=</span> <span class="n">name</span><span class="o">.[</span><span class="nn">String</span><span class="p">.</span><span class="n">length</span> <span class="n">name</span> <span class="o">-</span> <span class="mi">1</span><span class="o">]</span> <span class="k">in</span>
          <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">add</span> <span class="nn">Parser</span><span class="p">.</span><span class="n">binop_precedence</span> <span class="n">op</span> <span class="n">prec</span><span class="o">;</span>
      <span class="o">|</span> <span class="o">_</span> <span class="o">-&gt;</span> <span class="bp">()</span>
      <span class="k">end</span><span class="o">;</span>

      <span class="c">(* Create a new basic block to start insertion into. *)</span>
      <span class="k">let</span> <span class="n">bb</span> <span class="o">=</span> <span class="n">append_block</span> <span class="n">context</span> <span class="s2">&quot;entry&quot;</span> <span class="n">the_function</span> <span class="k">in</span>
      <span class="n">position_at_end</span> <span class="n">bb</span> <span class="n">builder</span><span class="o">;</span>

      <span class="k">try</span>
        <span class="k">let</span> <span class="n">ret_val</span> <span class="o">=</span> <span class="n">codegen_expr</span> <span class="n">body</span> <span class="k">in</span>

        <span class="c">(* Finish off the function. *)</span>
        <span class="k">let</span> <span class="o">_</span> <span class="o">=</span> <span class="n">build_ret</span> <span class="n">ret_val</span> <span class="n">builder</span> <span class="k">in</span>

        <span class="c">(* Validate the generated code, checking for consistency. *)</span>
        <span class="nn">Llvm_analysis</span><span class="p">.</span><span class="n">assert_valid_function</span> <span class="n">the_function</span><span class="o">;</span>

        <span class="c">(* Optimize the function. *)</span>
        <span class="k">let</span> <span class="o">_</span> <span class="o">=</span> <span class="nn">PassManager</span><span class="p">.</span><span class="n">run_function</span> <span class="n">the_function</span> <span class="n">the_fpm</span> <span class="k">in</span>

        <span class="n">the_function</span>
      <span class="k">with</span> <span class="n">e</span> <span class="o">-&gt;</span>
        <span class="n">delete_function</span> <span class="n">the_function</span><span class="o">;</span>
        <span class="k">raise</span> <span class="n">e</span>
</pre></div>
</div>
</dd>
<dt>toplevel.ml:</dt><dd><div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(*===----------------------------------------------------------------------===</span>
<span class="c"> * Top-Level parsing and JIT Driver</span>
<span class="c"> *===----------------------------------------------------------------------===*)</span>

<span class="k">open</span> <span class="nc">Llvm</span>
<span class="k">open</span> <span class="nc">Llvm_executionengine</span>

<span class="c">(* top ::= definition | external | expression | &#39;;&#39; *)</span>
<span class="k">let</span> <span class="k">rec</span> <span class="n">main_loop</span> <span class="n">the_fpm</span> <span class="n">the_execution_engine</span> <span class="n">stream</span> <span class="o">=</span>
  <span class="k">match</span> <span class="nn">Stream</span><span class="p">.</span><span class="n">peek</span> <span class="n">stream</span> <span class="k">with</span>
  <span class="o">|</span> <span class="nc">None</span> <span class="o">-&gt;</span> <span class="bp">()</span>

  <span class="c">(* ignore top-level semicolons. *)</span>
  <span class="o">|</span> <span class="nc">Some</span> <span class="o">(</span><span class="nn">Token</span><span class="p">.</span><span class="nc">Kwd</span> <span class="sc">&#39;;&#39;</span><span class="o">)</span> <span class="o">-&gt;</span>
      <span class="nn">Stream</span><span class="p">.</span><span class="n">junk</span> <span class="n">stream</span><span class="o">;</span>
      <span class="n">main_loop</span> <span class="n">the_fpm</span> <span class="n">the_execution_engine</span> <span class="n">stream</span>

  <span class="o">|</span> <span class="nc">Some</span> <span class="n">token</span> <span class="o">-&gt;</span>
      <span class="k">begin</span>
        <span class="k">try</span> <span class="k">match</span> <span class="n">token</span> <span class="k">with</span>
        <span class="o">|</span> <span class="nn">Token</span><span class="p">.</span><span class="nc">Def</span> <span class="o">-&gt;</span>
            <span class="k">let</span> <span class="n">e</span> <span class="o">=</span> <span class="nn">Parser</span><span class="p">.</span><span class="n">parse_definition</span> <span class="n">stream</span> <span class="k">in</span>
            <span class="n">print_endline</span> <span class="s2">&quot;parsed a function definition.&quot;</span><span class="o">;</span>
            <span class="n">dump_value</span> <span class="o">(</span><span class="nn">Codegen</span><span class="p">.</span><span class="n">codegen_func</span> <span class="n">the_fpm</span> <span class="n">e</span><span class="o">);</span>
        <span class="o">|</span> <span class="nn">Token</span><span class="p">.</span><span class="nc">Extern</span> <span class="o">-&gt;</span>
            <span class="k">let</span> <span class="n">e</span> <span class="o">=</span> <span class="nn">Parser</span><span class="p">.</span><span class="n">parse_extern</span> <span class="n">stream</span> <span class="k">in</span>
            <span class="n">print_endline</span> <span class="s2">&quot;parsed an extern.&quot;</span><span class="o">;</span>
            <span class="n">dump_value</span> <span class="o">(</span><span class="nn">Codegen</span><span class="p">.</span><span class="n">codegen_proto</span> <span class="n">e</span><span class="o">);</span>
        <span class="o">|</span> <span class="o">_</span> <span class="o">-&gt;</span>
            <span class="c">(* Evaluate a top-level expression into an anonymous function. *)</span>
            <span class="k">let</span> <span class="n">e</span> <span class="o">=</span> <span class="nn">Parser</span><span class="p">.</span><span class="n">parse_toplevel</span> <span class="n">stream</span> <span class="k">in</span>
            <span class="n">print_endline</span> <span class="s2">&quot;parsed a top-level expr&quot;</span><span class="o">;</span>
            <span class="k">let</span> <span class="n">the_function</span> <span class="o">=</span> <span class="nn">Codegen</span><span class="p">.</span><span class="n">codegen_func</span> <span class="n">the_fpm</span> <span class="n">e</span> <span class="k">in</span>
            <span class="n">dump_value</span> <span class="n">the_function</span><span class="o">;</span>

            <span class="c">(* JIT the function, returning a function pointer. *)</span>
            <span class="k">let</span> <span class="n">result</span> <span class="o">=</span> <span class="nn">ExecutionEngine</span><span class="p">.</span><span class="n">run_function</span> <span class="n">the_function</span> <span class="o">[||]</span>
              <span class="n">the_execution_engine</span> <span class="k">in</span>

            <span class="n">print_string</span> <span class="s2">&quot;Evaluated to &quot;</span><span class="o">;</span>
            <span class="n">print_float</span> <span class="o">(</span><span class="nn">GenericValue</span><span class="p">.</span><span class="n">as_float</span> <span class="nn">Codegen</span><span class="p">.</span><span class="n">double_type</span> <span class="n">result</span><span class="o">);</span>
            <span class="n">print_newline</span> <span class="bp">()</span><span class="o">;</span>
        <span class="k">with</span> <span class="nn">Stream</span><span class="p">.</span><span class="nc">Error</span> <span class="n">s</span> <span class="o">|</span> <span class="nn">Codegen</span><span class="p">.</span><span class="nc">Error</span> <span class="n">s</span> <span class="o">-&gt;</span>
          <span class="c">(* Skip token for error recovery. *)</span>
          <span class="nn">Stream</span><span class="p">.</span><span class="n">junk</span> <span class="n">stream</span><span class="o">;</span>
          <span class="n">print_endline</span> <span class="n">s</span><span class="o">;</span>
      <span class="k">end</span><span class="o">;</span>
      <span class="n">print_string</span> <span class="s2">&quot;ready&gt; &quot;</span><span class="o">;</span> <span class="n">flush</span> <span class="n">stdout</span><span class="o">;</span>
      <span class="n">main_loop</span> <span class="n">the_fpm</span> <span class="n">the_execution_engine</span> <span class="n">stream</span>
</pre></div>
</div>
</dd>
<dt>toy.ml:</dt><dd><div class="highlight-ocaml notranslate"><div class="highlight"><pre><span></span><span class="c">(*===----------------------------------------------------------------------===</span>
<span class="c"> * Main driver code.</span>
<span class="c"> *===----------------------------------------------------------------------===*)</span>

<span class="k">open</span> <span class="nc">Llvm</span>
<span class="k">open</span> <span class="nc">Llvm_executionengine</span>
<span class="k">open</span> <span class="nc">Llvm_target</span>
<span class="k">open</span> <span class="nc">Llvm_scalar_opts</span>

<span class="k">let</span> <span class="n">main</span> <span class="bp">()</span> <span class="o">=</span>
  <span class="n">ignore</span> <span class="o">(</span><span class="n">initialize_native_target</span> <span class="bp">()</span><span class="o">);</span>

  <span class="c">(* Install standard binary operators.</span>
<span class="c">   * 1 is the lowest precedence. *)</span>
  <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">add</span> <span class="nn">Parser</span><span class="p">.</span><span class="n">binop_precedence</span> <span class="sc">&#39;&lt;&#39;</span> <span class="mi">10</span><span class="o">;</span>
  <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">add</span> <span class="nn">Parser</span><span class="p">.</span><span class="n">binop_precedence</span> <span class="sc">&#39;+&#39;</span> <span class="mi">20</span><span class="o">;</span>
  <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">add</span> <span class="nn">Parser</span><span class="p">.</span><span class="n">binop_precedence</span> <span class="sc">&#39;-&#39;</span> <span class="mi">20</span><span class="o">;</span>
  <span class="nn">Hashtbl</span><span class="p">.</span><span class="n">add</span> <span class="nn">Parser</span><span class="p">.</span><span class="n">binop_precedence</span> <span class="sc">&#39;*&#39;</span> <span class="mi">40</span><span class="o">;</span>    <span class="c">(* highest. *)</span>

  <span class="c">(* Prime the first token. *)</span>
  <span class="n">print_string</span> <span class="s2">&quot;ready&gt; &quot;</span><span class="o">;</span> <span class="n">flush</span> <span class="n">stdout</span><span class="o">;</span>
  <span class="k">let</span> <span class="n">stream</span> <span class="o">=</span> <span class="nn">Lexer</span><span class="p">.</span><span class="n">lex</span> <span class="o">(</span><span class="nn">Stream</span><span class="p">.</span><span class="n">of_channel</span> <span class="n">stdin</span><span class="o">)</span> <span class="k">in</span>

  <span class="c">(* Create the JIT. *)</span>
  <span class="k">let</span> <span class="n">the_execution_engine</span> <span class="o">=</span> <span class="nn">ExecutionEngine</span><span class="p">.</span><span class="n">create</span> <span class="nn">Codegen</span><span class="p">.</span><span class="n">the_module</span> <span class="k">in</span>
  <span class="k">let</span> <span class="n">the_fpm</span> <span class="o">=</span> <span class="nn">PassManager</span><span class="p">.</span><span class="n">create_function</span> <span class="nn">Codegen</span><span class="p">.</span><span class="n">the_module</span> <span class="k">in</span>

  <span class="c">(* Set up the optimizer pipeline.  Start with registering info about how the</span>
<span class="c">   * target lays out data structures. *)</span>
  <span class="nn">DataLayout</span><span class="p">.</span><span class="n">add</span> <span class="o">(</span><span class="nn">ExecutionEngine</span><span class="p">.</span><span class="n">target_data</span> <span class="n">the_execution_engine</span><span class="o">)</span> <span class="n">the_fpm</span><span class="o">;</span>

  <span class="c">(* Do simple &quot;peephole&quot; optimizations and bit-twiddling optzn. *)</span>
  <span class="n">add_instruction_combination</span> <span class="n">the_fpm</span><span class="o">;</span>

  <span class="c">(* reassociate expressions. *)</span>
  <span class="n">add_reassociation</span> <span class="n">the_fpm</span><span class="o">;</span>

  <span class="c">(* Eliminate Common SubExpressions. *)</span>
  <span class="n">add_gvn</span> <span class="n">the_fpm</span><span class="o">;</span>

  <span class="c">(* Simplify the control flow graph (deleting unreachable blocks, etc). *)</span>
  <span class="n">add_cfg_simplification</span> <span class="n">the_fpm</span><span class="o">;</span>

  <span class="n">ignore</span> <span class="o">(</span><span class="nn">PassManager</span><span class="p">.</span><span class="n">initialize</span> <span class="n">the_fpm</span><span class="o">);</span>

  <span class="c">(* Run the main &quot;interpreter loop&quot; now. *)</span>
  <span class="nn">Toplevel</span><span class="p">.</span><span class="n">main_loop</span> <span class="n">the_fpm</span> <span class="n">the_execution_engine</span> <span class="n">stream</span><span class="o">;</span>

  <span class="c">(* Print out all the generated code. *)</span>
  <span class="n">dump_module</span> <span class="nn">Codegen</span><span class="p">.</span><span class="n">the_module</span>
<span class="o">;;</span>

<span class="n">main</span> <span class="bp">()</span>
</pre></div>
</div>
</dd>
<dt>bindings.c</dt><dd><div class="highlight-c notranslate"><div class="highlight"><pre><span></span><span class="cp">#include</span> <span class="cpf">&lt;stdio.h&gt;</span><span class="cp"></span>

<span class="cm">/* putchard - putchar that takes a double and returns 0. */</span>
<span class="k">extern</span> <span class="kt">double</span> <span class="n">putchard</span><span class="p">(</span><span class="kt">double</span> <span class="n">X</span><span class="p">)</span> <span class="p">{</span>
  <span class="n">putchar</span><span class="p">((</span><span class="kt">char</span><span class="p">)</span><span class="n">X</span><span class="p">);</span>
  <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>

<span class="cm">/* printd - printf that takes a double prints it as &quot;%f\n&quot;, returning 0. */</span>
<span class="k">extern</span> <span class="kt">double</span> <span class="n">printd</span><span class="p">(</span><span class="kt">double</span> <span class="n">X</span><span class="p">)</span> <span class="p">{</span>
  <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%f</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="n">X</span><span class="p">);</span>
  <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
</div>
</dd>
</dl>
<p><a class="reference external" href="OCamlLangImpl7.html">Next: Extending the language: mutable variables / SSA
construction</a></p>
</div>
</div>


            <div class="clearer"></div>
          </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="OCamlLangImpl7.html" title="7. Kaleidoscope: Extending the Language: Mutable Variables"
             >next</a> |</li>
        <li class="right" >
          <a href="OCamlLangImpl5.html" title="5. Kaleidoscope: Extending the Language: Control Flow"
             >previous</a> |</li>
  <li><a href="http://llvm.org/">LLVM Home</a>&nbsp;|&nbsp;</li>
  <li><a href="../index.html">Documentation</a>&raquo;</li>

          <li class="nav-item nav-item-1"><a href="index.html" >LLVM Tutorial: Table of Contents</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href=""><span class="section-number">6. </span>Kaleidoscope: Extending the Language: User-defined Operators</a></li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2003-2020, LLVM Project.
      Last updated on 2020-09-20.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 3.2.1.
    </div>
  </body>
</html>